虽然远没有达到这个水平，但是据说Atcoder思维难度大，代码难度小，适合我这种不会打字的选手，所以试着做一做
不知道能做几题啊
在完全自己做出来的题前面打"√“（目前好像还没有诶。。。o(╥﹏╥)o）
计数器菌：7/104
如果两个字符确定相等就在中间连一条边，那么所有字符相同就等价于使整个图联通
然后发现至少要\(n-1\)条边，而事实上一个序列贡献的边数最大为\(\frac n 2\)条，而且一旦序列里有一个奇数贡献的边数就会减去\(\frac 1 2\)，所以如果原始序列出现\(\gt 2\)个奇数，那么就不可行
一个偶数序列，整体向左平移一个之后，正好全部连起来了
如果有奇数怎么办？因为至多两个奇数，我们把奇数放到两边，中间全是偶数，那么可以像刚才那样做，两边的奇数这样做也符合题意。
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=200;
int n,m;
int a[maxn];
int main(){
#ifdef LZT
// freopen("in","r",stdin);
#endif
int num=0;
n=read();m=read();
rep(i,1,m){
a[i]=read();
if(a[i]&1) num++;
}
if(num>2){
puts("Impossible");
return 0;
}
for(int i=1;i<=m;i++)
if(a[i]&1){
if(a[1]&1) swap(a[i],a[m]);
else swap(a[i],a[1]);
}
rep(i,1,m) cout<<a[i]<<' ';
cout<<endl;
a[1]++;a[m]--;
if(a[m]==0) m--;
if(m>=2){
cout<<m<<endl;
rep(i,1,m) cout<<a[i]<<' ';
cout<<endl;
}
else{
if(n<=2){
cout<<1<<endl;
cout<<n<<endl;
}
else{
cout<<2<<endl;
cout<<n-1<<' '<<1<<endl;
}
}
return 0;
}我们发现答案其实就是要求\(\sum_{i=1}^{n-1}\sum_{j=i+1}^nC_{a_i+a_j+b_i+b_j}^{a_i+a_j}\)
然后知道\(C_{a_i+a_j+b_i+b_j}^{a_i+a_j}\)实际上就是点\((-a_i,-b_i)\)走到\((a_j,b_j)\)的方案数
那么原式等价于求点集\((-a_i,-b_i)\)到点集\((a_i,b_i)\)两两的方案数的和减去所有点走到他对应的对称点的方案数（即\(i=j\)的方案数）除以2（每个方案被算了两次）
所以dp就可以了，可以想象中建立一个超级源点连向所有的\((-a_i,-b_i)\)和超级汇点连向所有的\((a_i,b_i)\)，就可以求出方案数
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int mod=1000000007;
const int maxn=200200;
const int maxm=2200;
int n;
int a[maxn],b[maxn];
int dp[maxm*2][maxm*2];
int flag[maxm*2][maxm*2];
int ans;
void pl(int &a,ll b){
a=(a+b%mod)%mod;
}
void mi(int &a,ll b){
a=a-b%mod;
while(a<0) a+=mod;
a=a%mod;
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
n=read();
rep(i,1,n) a[i]=read(),b[i]=read();
rep(i,1,n){
flag[2100-a[i]][2100-b[i]]++;
flag[a[i]+2100][b[i]+2100]++;
}
rep(i,1,4200){
rep(j,1,4200){
pl(dp[i][j],dp[i-1][j]);
pl(dp[i][j],dp[i][j-1]);
if(flag[i][j] && i<=2100 && j<=2100) pl(dp[i][j],flag[i][j]);
if(flag[i][j] && i>=2100 && j>=2100) pl(ans,dp[i][j]*1ll*flag[i][j]);
}
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
rep(i,0,4200){
rep(j,0,4200){
if(i==0 && j==0) continue;
if(i) pl(dp[i][j],dp[i-1][j]);
if(j) pl(dp[i][j],dp[i][j-1]);
}
}
rep(i,1,n)
mi(ans,dp[a[i]+a[i]][b[i]+b[i]]);
ans=ans*500000004ll%mod;
cout<<ans<<endl;
return 0;
}先考虑暴力做法，对于一组询问\((x,y,z)\)，我们暴力将边从小到大加入图里，当\(x\)所在的连通块点数加\(y\)所在连通块点数（当\(x\)和\(y\)在不同连通块时才加）第一次\(\geq z\)时，当前边的序号就是答案
所以答案是有单调性的，可以二分
然后每一组都二分肯定不行，所以整体二分
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=100100;
int n,m,Q;
pii edge[maxn];
struct query
{
int ind;
int a,b,num;
void re(int x){
a=read(),b=read(),num=read();
ind=x;
}
} q[maxn],tmp[maxn];
int ans[maxn],fa[maxn],sz[maxn];
bool ok[maxn];
pii sta[maxn];int cnt;
inline int fp(int x){if(x==fa[x]) return x;return fp(fa[x]);}
void solve(int l,int r,int le,int ri){
//cout<<l<<' '<<r<<' '<<le<<' '<<ri<<endl;
if(l==r){
rep(i,le,ri) ans[q[i].ind]=l;
int x=edge[l].fi,y=edge[l].se;
x=fp(x);y=fp(y);
if(x!=y){
if(sz[x]>sz[y])swap(x,y);
fa[x]=y;sz[y]+=sz[x];
}
return;
}
int md=(l+r)>>1;cnt=0;
rep(i,l,md){
int x=edge[i].fi,y=edge[i].se;
x=fp(x);y=fp(y);
if(x!=y){
if(sz[x]>sz[y]) swap(x,y);
fa[x]=y;sz[y]+=sz[x];
sta[++cnt]=mp(x,y);
}
}
rep(i,le,ri){
query &nw=q[i];
int a=nw.a,b=nw.b;
//cout<<a<<' '<<b<<endl;
a=fp(a);b=fp(b);
//cout<<i<<' '<<a<<' '<<b<<' ';
int nww=0;
if(a==b) nww=sz[a];else nww=sz[a]+sz[b];
if(nww>=nw.num) ok[i]=1;else ok[i]=0;
//cout<<ok[i]<<endl;
}
int pos=le-1;
rep(i,le,ri)
if(ok[i]) tmp[++pos]=q[i];
pos=ri+1;
rrep(i,ri,le)
if(!ok[i]) tmp[--pos]=q[i];
//cout<<le<<' '<<ri<<' '<<pos<<endl;
rep(i,le,ri) q[i]=tmp[i];
while(cnt){
int x=sta[cnt].fi,y=sta[cnt].se;
fa[x]=x;sz[y]-=sz[x];cnt--;
}
solve(l,md,le,pos-1);solve(md+1,r,pos,ri);
}
int main(){
n=read(),m=read();
rep(i,1,m) edge[i].fi=read(),edge[i].se=read();
Q=read();
rep(i,1,Q) q[i].re(i);
rep(i,1,n) sz[i]=1,fa[i]=i;
solve(1,m,1,Q);
rep(i,1,Q) printf("%d\n",ans[i]);
return 0;
}
/*
5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5
*/真难想的博弈题
首先先想状态
不知怎么想到把他表示成图形
就是我们先排序 然后把一堆石子想象成一个石子个数*1的矩形。 把矩形从高到低排列变成一个图形。
然后操作就变成了删掉最左边一列或者最下面一行
假设有一个点当前在\((1,1)\)，那么每次操作他向右或者向上移动一个，不能移动者输
那么给每个点标记上\(o\)或者\(x\)，分别表示必胜和必败
所有最外层的角上（意会）一定都是\(x\)
然后发现当\((x+1,y+1)\)不是最外层的点的时候，\((x,y)\)和\((x+1,y+1)\)的标记相同
所以算法就是先把\((1,1)\)向右上方移动直到边界为止，然后要么向上要么向右，如果都是必败那么就是必败，否则必胜
向上向右因为只有一个方向所以只奇偶性有关
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=100100;
int n;
int a[maxn];
int main(){
n=read();
rep(i,1,n) a[i]=read();
sort(a+1,a+n+1);
reverse(a+1,a+n+1);
rep(i,1,n+1){
if(a[i]<i){
i--;
int num=0;
for(int j=i+1;j<=n;j++)
if(a[j]==i) num++;
if(num&1){
puts("First");
return 0;
}
if((a[i]-i)&1) puts("First");
else puts("Second");
return 0;
}
}
}直接\(\text{dp}\)
把“把每种颜色的最左边的球变为0”理解成“任意前缀的颜色数<0的数量”
然后放球的时候一次把一种颜色的球放完，把“放在后面”变成“插入这么多个新的球”，放完一种颜色的 \(k-1\) 个球之后才能放 \(0\)
然后 \(f[i][j]\) 表示当前放前 \(i\) 种颜色（我们固定先放颜色1，再放颜色2，最后乘上 \(\text{fac[i]}\) 就可以了），还没放的 \(\text{0}\) 的个数是 \(j\) 的方案数
那么首先可以在最前面加一个 \(0\) ，即 \(f[i][j]=f[i][j+1]\)
然后可以新增一种颜色，从 \(f[i-1][j-1]\) 转移过来，我们知道当前的球的个数是 \((i-1)*k-(j-1)\) 个，要放入 \(k-1\) 个新的球，运用插板法，就是 \(C_{(i-1)*k-(j-1)+k-1-1}^{(i-1)*k-j}=C_{i*k-j-1}^{k-2}\) 种方案
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int mod=1e9+7;
const int maxn=3050;
int n,k;
ll f[maxn][maxn];
ll fac[maxn*maxn],inv[maxn*maxn];
inline int C(int x,int y){
if(x<y) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
n=read(),k=read();
if(k==1){
puts("1");
return 0;
}
fac[0]=1;
rep(i,1,3000*3000) fac[i]=fac[i-1]*i%mod;
inv[0]=inv[1]=1;
rep(i,2,3000*3000) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
rep(i,1,3000*3000) inv[i]=inv[i]*inv[i-1]%mod;
f[0][0]=1;
rep(i,1,n){
rrep(j,i,0){
f[i][j]=f[i][j+1]%mod;
if(j){
f[i][j]+=f[i-1][j-1]*C(i*k-j-1,k-2)%mod;
f[i][j]%=mod;
}
}
}
cout<<f[n][0]*fac[n]%mod;
return 0;
}首先把每个数分解质因数，然后把指数模3，称变换之后的数为原来的数的最简数
对于一个最简数，存在一个补数，定义为与最简数相乘是立方数的最小数
对于一个最简数代表的数集和其补数代表的数集，我们选取较大的一个
如果一个数和其补数相同，那么只能选1个
关键在于分解质因数，我们先筛出来3000以内的质数，然后如果一个数把3000以下的数除完之后不为1，那么肯定是完全平方数或者质数，分别判断一下即可（如果是两个3000以上的质数相乘，那么不可能对答案产生贡献，所以可以忽略）
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register ll i=(ll)(j);i<=(ll)(k);i++)
#define rrep(i,j,k) for(register ll i=(ll)(j);i>=(ll)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const ll maxn=100100;
int n;
ll a[maxn];
bool isp[maxn];
int pr[maxn],cnt;
int num[maxn][500];
set<ll> s;
map<ll,int> M;
map<ll,int> ind;
map<ll,int> used;
void init(){
memset(isp,1,sizeof(isp));
isp[0]=isp[1]=0;
rep(i,2,3000){
if(isp[i]){
pr[++cnt]=i;
}
for(ll j=1;j<=cnt && i*pr[j]<=3000;j++){
isp[i*pr[j]]=0;
if(i%pr[j]==0) break;
}
}
}
bool pd(ll x){
for(ll i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
int main(){
#ifdef LZT
//freopen("in","r",stdin);
#endif
ll ans=0;
n=read();
rep(i,1,n) a[i]=read();
init();
rep(i,1,n){
ll t=a[i];
rep(j,1,cnt){
while(t%pr[j]==0){
t=t/pr[j];
num[i][j]++;
}
num[i][j]%=3;
}
if(t>pr[cnt]){
ll nw=sqrt(t);
if(nw*nw==t){
num[i][cnt+1]=nw;
num[i][cnt+2]=2;
t=1;
}
else{
if(t<=100000 && pd(t)){
num[i][cnt+1]=t;
num[i][cnt+2]=1;
t=1;
}
}
}
ll tt=1;
rep(j,1,cnt){
if(num[i][j]==1) tt=tt*pr[j];
else if(num[i][j]==2) tt=tt*pr[j]*pr[j];
}
if(num[i][cnt+1]){
tt=tt*num[i][cnt+1];
if(num[i][cnt+2]==2) tt=tt*num[i][cnt+1];
}
if(t==1){
s.insert(tt);
M[tt]++;
ind[tt]=i;
}
else ans++;
}
for(set<ll>::iterator it=s.begin();it!=s.end();it++){
ll nw=*it;
if(used[nw]) continue;
used[nw]=1;
ll i=ind[nw];
ll t=1;
for(ll j=1;j<=cnt;j++){
if(num[i][j]==1) t=t*pr[j]*pr[j];
else if(num[i][j]==2) t=t*pr[j];
}
if(num[i][cnt+1]){
if(num[i][cnt+2]==1) t=t*num[i][cnt+1]*num[i][cnt+1];
else t=t*num[i][cnt+1];
}
if(nw==t) ans++;
else ans+=max(M[nw],M[t]);
used[t]=1;
}
cout<<ans<<endl;
return 0;
}借鉴了\(\text{fizzydavid}\)的代码，写的很精巧
题目就是说有一个数字串S，初始长度为n，是1 2 3 4 …… n，有m次操作，每次操作给你一个正整数a[i]，你先把S无穷重复，然后把前a[i]截取出来成为新的S。
求m次操作后，每个数字在S中出现的次数。
我们倒着考虑
首先如果 \(a[i] \ge a[i+1]\) 那么 \(a[i]\) 可以直接删掉，显然没用
所以我们先用单调栈把 \(a\) 变成单调递增的
然后每一次操作等价于把前一次的序列复制几次然后加上一个前缀
我们倒着考虑，用一个 \(\text{pair}\) 表示我们当前给长度为 \(\text{pair.first}\) 的前缀重复加了 \(\text{pair.second}\) 次
那么一开始，考虑最后一次操作，等价于插入 \(\text{pair<a[cnt],1>}\) 就是整个加了1次
然后考虑当前操作的长度为 \(cur\) ，对于每一个存在的 \(\text{pair}\) ，我们会将其更新，因为实际上这个 \(pair\) 可以由当前的 \(\text{cur}\) 得到，所以我们计算当前的 \(cur\) 这个前缀在每一个存在的 \(\text{pair}\) 中一共出现几次，也就是
sum+=nw.se*(nw.fi/cur);
当然如果 \(nw.fi\) 不是\(cur\) 的倍数，那么会出现一个多余的小于 \(cur\) 的前缀，这个前缀出现了 \(nw.se\) 次，长度就是 \(\text{nw.fi%cur}\)
然后我们使用partial sum的方法，最后倒着加起来就好了
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
priority_queue<pair<ll,ll> > pq;
ll n,q;
ll st[100100],cnt;
ll ans[100100];
int main(){
#ifdef LZT
// freopen("in","r",stdin);
#endif
n=read(),q=read();
st[++cnt]=n;
for(int i=1;i<=q;i++){
ll x=read();
while(st[cnt]>=x) cnt--;
st[++cnt]=x;
}
pq.push(mp(st[cnt],1));
for(int i=cnt;i>=1;i--){
ll sum=0,cur=st[i];
while(!pq.empty() && pq.top().fi>cur){
pair<ll,ll> nw=pq.top();pq.pop();
sum+=nw.se*(nw.fi/cur);
if(nw.fi%cur) pq.push(mp(nw.fi%cur,nw.se));
}
pq.push(mp(cur,sum));
}
while(!pq.empty()) ans[pq.top().fi]+=pq.top().se,pq.pop();
rrep(i,n,1) ans[i]+=ans[i+1];
rep(i,1,n) printf("%lld \n",ans[i]);
return 0;
}原文：https://www.cnblogs.com/wawawa8/p/9716143.html