D1T1: 每30位压成一个int，然后压位线段树就可以过了。
#include <bits/stdc++.h> #define gc getchar() #define N 4500009 #define mid (l+r>>1) #define ll long long using namespace std; const int Max=1<<30; int n,m,t1,t2,t3; struct node { int val; node *lc,*rc; void up() { if (lc->val==rc->val) val=lc->val; else val=-1; } void down() { if (val!=-1) lc->val=rc->val=val; } int ins(int l,int r,int x,int y,int ret=0) { if (l==r) { val+=y; if (val>=Max) { val-=Max; return 1; } if (val<0) { val+=Max; return -1; } return 0; } if (val==0&&l==x&&y==-1) { val=Max-1; return -1; } if (val==Max-1&&l==x&&y==1) { val=0; return 1; } down(); if (x<=mid) { ret=lc->ins(l,mid,x,y); if (ret) ret=rc->ins(mid+1,r,mid+1,ret); } else ret=rc->ins(mid+1,r,x,y); up(); return ret; } int get(int l,int r,int x) { if (l==r) return val; down(); if (x<=mid) return lc->get(l,mid,x); else return rc->get(mid+1,r,x); } }a[N],*now=a,*root; node *build(int l,int r) { node *Now=now++; Now->val=0; if (l==r) return Now; Now->lc=build(l,mid); Now->rc=build(mid+1,r); return Now; } int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } int main() { m=read(),t1=read(),t2=read(),t3=read(); n=m+32; root=build(0,n); while (m--) { int op=read(); if (op==1) { int a=read(),b=read(); if (a>=0) { int a1=((ll)a<<(b0))&(Max-1); int a2=a>>(30-b0); int b1=b/30,b2=b1+1; if (a1) root->ins(0,n,b1,a1); if (a2) root->ins(0,n,b2,a2); } else { a=-a; int a1=((ll)a<<(b0))&(Max-1); int a2=a>>(30-b0); int b1=b/30,b2=b1+1; if (a1) root->ins(0,n,b1,-a1); if (a2) root->ins(0,n,b2,-a2); } } else { int a=read(); int ans=root->get(0,n,a/30); printf("%d\n",(ans>>(a0))&1); } } return 0; }D1T2： 根据miaom大的说法，因为拆开的操作很少，所以每次暴力维护所有 len≤50 的字符串就可以了， hash+hash 表（注意双哈希）
#include <bits/stdc++.h> #define gc getchar() #define ll long long #define A 7 #define MOD 5614657 #define Mod 44917381 #define mod 998244353 #define N 200009 #define M 10000009 #define DEBUG 0 #define debug() cerr<<"wrong"<<endl using namespace std; int n,m,a[N],fa[N],son[N],b[M],p[55][2]; struct HASH { #define MM 10000010 int number,first[MOD]; struct edge { int y,next,val; edge(int y=0,int next=0,int val=0):y(y),next(next),val(val){} }e[MM]; inline void add(int x,int y) { e[++number]=edge(y,first[x],1); first[x]=number; } inline void ins(int x,int y) { for (int i=first[x];i;i=e[i].next) if (e[i].y==y) { e[i].val++; return; } add(x,y); } inline void del(int x,int y) { for (int i=first[x];i;i=e[i].next) if (e[i].y==y) { e[i].val--; return; } } inline int find(int x,int y) { for (int i=first[x];i;i=e[i].next) if (e[i].y==y) return e[i].val; return 0; } }ha; inline int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } inline void link(int x,int y) { fa[y]=x,son[x]=y; int last=x,next=y,len1=1,len2=1,len=0; for (int i=1;i<=48&&fa[last];i++) last=fa[last],len1++; for (int i=1;i<=48&&son[next];i++) next=son[next],len2++; for (int i=1;i<=len1+len2;i++) b[++len]=a[last],last=son[last]; for (int i=1;i<=len1;i++) { int now=0,Now=0; for (int j=i;j<=len1;j++) { now=(now*A%MOD+b[j])%MOD; Now=(Now*A%Mod+b[j])%Mod; } for (int j=len1+1;j-i+1<=50&&j<=len;j++) { now=(now*A%MOD+b[j])%MOD; Now=(Now*A%Mod+b[j])%Mod; ha.ins(now,Now); } } } inline void cut(int x,int y) { int last=x,next=y,len1=1,len2=1,len=0; for (int i=1;i<=48&&fa[last];i++) last=fa[last],len1++; for (int i=1;i<=48&&son[next];i++) next=son[next],len2++; for (int i=1;i<=len1+len2;i++) b[++len]=a[last],last=son[last]; for (int i=1;i<=len1;i++) { int now=0,Now=0; for (int j=i;j<=len1;j++) { now=(now*A%MOD+b[j])%MOD; Now=(Now*A%Mod+b[j])%Mod; } for (int j=len1+1;j-i+1<=50&&j<=len;j++) { now=(now*A%MOD+b[j])%MOD; Now=(Now*A%Mod+b[j])%Mod; ha.del(now,Now); } } fa[y]=son[x]=0; } inline int solve() { int len=0,k,now=0,Now=0; char ch; while (ch=gc,ch<'1'||ch>'6'); while (ch!=' ') b[++len]=ch-'0',ch=gc; k=read(); for (int i=1;i<=k;i++) { now=(now*A%MOD+b[i])%MOD; Now=(Now*A%Mod+b[i])%Mod; } int ans=ha.find(now,Now); for (int i=2;i<=len-k+1;i++) { now=(now-(ll)b[i-1]*p[k-1][0]%MOD+MOD)%MOD; now=(now*A%MOD+b[i+k-1])%MOD; Now=(Now-(ll)b[i-1]*p[k-1][1]%Mod+Mod)%Mod; Now=(Now*A%Mod+b[i+k-1])%Mod; ans=(ll)ans*ha.find(now,Now)%mod; if (ans==0) break; } return ans; } int main() { if (DEBUG) { freopen("queue25.in","r",stdin); freopen("queue25.out","w",stdout); } n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(),ha.ins(a[i],a[i]); p[0][0]=p[0][1]=1; for (int i=1;i<=50;i++) p[i][0]=p[i-1][0]*A%MOD,p[i][1]=p[i-1][1]*A%Mod; while (m--) { int op=read(); if (op==1) { int x=read(),y=read(); link(x,y); } if (op==2) { int x=read(),y=son[x]; cut(x,y); } if (op==3) printf("%d\n",solve()); } return 0; }然而有些网站跑得慢，过不了，所以就需要sam来维护。
#include <bits/stdc++.h> #define gc getchar() #define ll long long #define mod 998244353 #define N 4500009 #define M 10000009 #define DEBUG 1 #define debug() cerr<<"wrong"<<endl using namespace std; int n,m,a[N],fa[N],Son[N],b[M]; int son[N][6],fail[N],w[N]; int cnt; void init() { cnt=1; for (int i=0;i<6;i++) son[cnt][i]=0; fail[cnt]=w[cnt]=0; } int go(int x,int k) { if (!son[x][k]) fail[son[x][k]=++cnt]=son[fail[x]][k]; return son[x][k]; } inline int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } inline void link(int x,int y) { fa[y]=x,Son[x]=y; int last=x,next=y,len1=1,len2=1,len=0; for (int i=1;i<=48&&fa[last];i++) last=fa[last],len1++; for (int i=1;i<=48&&Son[next];i++) next=Son[next],len2++; for (int i=1;i<=len1+len2;i++) b[++len]=a[last],last=Son[last]; for (int i=2,j,k;i<=50&&i<=len;i++)//i=added string's length { int now=1; for (j=max(1,len1-i+2),k=i;--k;j++) now=son[now][b[j]]; for (;j<=len&&j-i+1<=len1;j++) { now=go(now,b[j]); w[now]++; now=fail[now]; } } } inline void cut(int x,int y) { int last=x,next=y,len1=1,len2=1,len=0; for (int i=1;i<=48&&fa[last];i++) last=fa[last],len1++; for (int i=1;i<=48&&Son[next];i++) next=Son[next],len2++; for (int i=1;i<=len1+len2;i++) b[++len]=a[last],last=Son[last]; for (int i=1,k=x;i<50&&k;k=fa[k],i++)//i=deleted string's length { int now=1; for (int p=k,j=1;j<=50&&p;j++,p=Son[p]) { now=son[now][a[p]]; if (j>i) w[now]--;//p is behind x } } fa[y]=Son[x]=0; } inline int solve() { int len=0,k; char ch; while (ch=gc,ch<'1'||ch>'6'); while (ch!=' ') b[++len]=ch-'1',ch=gc; k=read(); int ans=1,now=1; for (int i=1;i<=len;i++) { if (!son[now][b[i]]) { ans=0; break; } now=son[now][b[i]]; if (i>=k) ans=(ll)ans*w[now]%mod,now=fail[now]; } return ans; } int main() { if (DEBUG) { freopen("queue25.in","r",stdin); freopen("queue25.out","w",stdout); } n=read(),m=read(); init(); for (int i=1;i<=n;i++) { a[i]=read()-1; if (!son[1][a[i]]) fail[son[1][a[i]]=++cnt]=1; w[son[1][a[i]]]++; } while (m--) { int op=read(); if (op==1) { int x=read(),y=read(); link(x,y); } if (op==2) { int x=read(),y=Son[x]; cut(x,y); } if (op==3) printf("%d\n",solve()); } return 0; }D1T3： 原问题可以转化为 Sdanger≤k 的答案 首先 dp[i][j] 表示宽度为 j ，前i−1行全是 danger ，最后 sdanger≤k 的概率。 所以上面的答案就是 dp[1][n] 然后这个可以比较容易 dp 转移。 然后可以算出 2到1001 的 dp ，这是 O(k2logk) 的。 然后线性其次递推，用一些姿势可以算出第 1 行的答案。 （反正我还不会）
#include <bits/stdc .h> #define ll long long #define mod 998244353 #define N 2009 using namespace std; int n,k,x,y,dp[N][N],pw[N],p,f[N],g[N],a[N],b[N],c[N]; int ksm(int x,int y,int ret=1) { for (;y;y>>=1,x=(ll)x*x%mod) if (y&1) ret=(ll)ret*x%mod; return ret; } void mul(int n,int *a,int *b) { memset(c,0,sizeof(c)); for (int i=0;i<=n;i ) for (int j=0;j<=n;j ) c[i j]=(c[i j] (ll)a[i]*b[j]%mod)%mod; for (int i=2*n;i>n;i--) for (int j=1;j<=n 1;j ) c[i-j]=(c[i-j] (ll)c[i]*g[j]%mod)%mod; for (int i=0;i<=n;i ) a[i]=c[i]; } int solve(int limit) { if (!limit) return ksm(mod 1-p,n); memset(dp,0,sizeof(dp)); dp[limit 1][0]=1; dp[limit 1][1]=pw[limit]; for (int i=limit;i;i--) { for (int j=0;j<=limit;j ) dp[i][j]=dp[i 1][j]; for (int j=1;(i-1)*j<=limit&&j<=limit;j ) for (int x=1;x<=j;x ) dp[i][j]=(dp[i][j] (ll)dp[i 1][x-1]*dp[i][j-x]%mod*pw[i-1]%mod)%mod; } if (n<=limit) return dp[1][n]; for (int i=1;i<=limit 1;i ) g[i]=(ll)dp[2][i-1]*(mod 1-p)%mod; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); a[0]=1,b[1]=1; for (int i=n 1;i;i>>=1) { if (i&1) mul(limit,a,b); mul(limit,b,b); }//calculate the coefficients int ans=0; memset(f,0,sizeof(f)); f[0]=ksm(mod 1-p,mod-2);//f[0]=1/(1-p) for (int i=1;i<=limit 1;i ) f[i]=dp[1][i-1]; for (int i=0;i<=limit;i ) ans=(ans (ll)f[i]*a[i]%mod)%mod; return ans; } int main() { scanf("%d%d%d%d",&n,&k,&x,&y); p=(ll)x*ksm(y,mod-2)%mod; pw[0]=mod 1-p; for (int i=1;i<N;i ) pw[i]=(ll)pw[i-1]*p%mod; printf("%d\n",(solve(k)-solve(k-1) mod)%mod); return 0; }D2T1： 就是一道2-sat简单题。。（然而我没做出来） 枚举x为 a 还是b地图，然后直接2-sat模板上就好了。 时间复杂度 O(2d(n+m)) （据说 3d 在现场也可以过）
#include <bits/stdc++.h> #define gc getchar() #define N 50009 #define mid (l+r>>1) #define ll long long using namespace std; const char ans[3][2]={{'B','C'},{'A','C'},{'A','B'}}; int n,d,pos[10],num,mp[N],m,first[N<<1],number; int dfn[N<<1],low[N<<1],sta[N<<1],top,vis[N<<1],col[N<<1],col_num,cnt; int First[N<<1],Number,ds[N<<1],choose[N<<1],Ans[N]; vector<int> opp[N<<1],color[N<<1]; queue<int> q; struct in_edge { int x,hx,y,hy; }Ed[N<<1]; struct edge { int from,to,next; void add(int x,int y) { from=x,to=y,next=first[x],first[x]=number; } }e[N<<2]; struct Edge { int from,to,next; void add(int x,int y) { from=x,to=y,next=First[x],First[x]=Number; } }E[N<<2]; int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } void get_map() { for (int i=1;i<=(n<<1);i++) First[i]=first[i]=0; number=Number=0; for (int i=1;i<=m;i++) { int x,y; if (mp[Ed[i].x]<2) x=(Ed[i].hx==2); else x=(Ed[i].hx==1); x+=2*Ed[i].x-1; if (mp[Ed[i].y]<2) y=(Ed[i].hy==2); else y=(Ed[i].hy==1); y+=2*Ed[i].y-1; if (Ed[i].x==Ed[i].y) { if (Ed[i].hx==Ed[i].hy) continue; else { if (Ed[i].hx==mp[Ed[i].x]) continue; else e[++number].add(x,4*Ed[i].x-x-1); } } if (mp[Ed[i].x]==Ed[i].hx) continue; if (mp[Ed[i].y]==Ed[i].hy) { e[++number].add(x,4*Ed[i].x-x-1); continue; } e[++number].add(x,y); e[++number].add(4*Ed[i].y-y-1,4*Ed[i].x-x-1); } } void Tarjan(int x) { dfn[x]=++cnt; low[x]=cnt; vis[x]=1; sta[++top]=x; for (int i=first[x];i;i=e[i].next) { int temp=e[i].to; if (!dfn[temp]) { Tarjan(temp); low[x]=min(low[x],low[temp]); } else if (vis[temp]) low[x]=min(low[x],dfn[temp]); } if (dfn[x]==low[x]) { vis[x]=0; col[x]=++col_num; color[col_num].push_back(x); while (sta[top]!=x) { col[sta[top]]=col_num; color[col_num].push_back(sta[top]); vis[sta[top--]]=0; } top--; } } bool solve() { top=cnt=col_num=0; for (int i=1;i<=(n<<1);i++) choose[i]=ds[i]=dfn[i]=low[i]=vis[i]=0; for (int i=1;i<=(n<<1);i++) opp[i].clear(),color[i].clear(); for (int i=1;i<=(n<<1);i++) if (!dfn[i]) Tarjan(i); for (int i=1;i<=number;i++) if (col[e[i].to]!=col[e[i].from]) { E[++Number].add(col[e[i].to],col[e[i].from]); ds[col[e[i].from]]++; } for (int i=1;i<=n;i++) { if (col[i*2-1]==col[i*2]) return 0; opp[col[i*2-1]].push_back(col[i*2]); opp[col[i*2]].push_back(col[i*2-1]); } while (!q.empty()) q.pop(); for (int i=1;i<=col_num;i++) if (ds[i]==0) q.push(i); for (int l=1;l<=col_num;l++) { int now=q.front(); //cout<<now<<endl; q.pop(); if (!choose[now]) { choose[now]=1; for (int i=0;i<color[now].size();i++) Ans[(color[now][i]+1)>>1]=(color[now][i]+1)&1; for (int i=0;i<opp[now].size();i++) choose[opp[now][i]]=2; } for (int i=First[now];i;i=E[i].next) if (!(--ds[E[i].to])) q.push(E[i].to); } return 1; } void print() { for (int i=1;i<=n;i++) putchar(ans[mp[i]][Ans[i]]); puts(""); } int main() { n=read(),d=read(); for (int i=1;i<=n;i++) { char ch; while (ch=gc,ch!='x'&&ch!='a'&&ch!='b'&&ch!='c'); if (ch=='x') pos[++num]=i; else mp[i]=ch-'a'; } m=read(); for (int i=1;i<=m;i++) { char ch; Ed[i].x=read(); while (ch=gc,ch!='A'&&ch!='B'&&ch!='C'); Ed[i].hx=ch-'A'; Ed[i].y=read(); while (ch=gc,ch!='A'&&ch!='B'&&ch!='C'); Ed[i].hy=ch-'A'; } for (int now=0;now<(1<<d);now++) { for (int i=1;i<=d;i++) mp[pos[i]]=(now>>(i-1))&1; get_map(); if (solve()) { print(); return 0; } } puts("-1"); return 0; }D2T2&&D2T3： 一道费用流神题，一道计算几何神题，反正我不会写。。。（T2可能还有一丝希望） （未完待续）
