[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash，然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表示 $S_i$ 与上一个相同字符的距离（如果不存在则为 $i$ ），然后当比较后缀 $i$ 和后缀 $j$ 时，把 $a_i$ 到 $a_n$ 中 $k-a_k<i$ 的那些位置改成 $0$ ，后缀 $j$ 同理，然后就可以直接比较 $a_{[i,n]}$ 和 $a_{[j,n]}$ 了。由于只有小写字符，因此最多只有 $26$ 个位置需要改成 $0$ ，所以如果把后缀 $i$ 和后缀 $j$ 结合起来考虑，会把 $a$ 分为 $52$ 个段，对于段的分割节点，我们特殊判断，而分割节点中间的连续段我们可以直接利用 $LCP$ 判断是否全相同。这样每次比较的复杂度就是 $O(26)$ 了，直接sort就可以得到排名，复杂度 $O(26n\log_2n)$ 。示例程序#include<cstdio> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=200000,maxi=26,LOG=17; int n,a[maxn+5],lst[maxi],ID[maxn+5];char s[maxn+5]; int SA[maxn+5],rk[maxn+5],ha[maxn+5],sc[(maxn<<1)+5]; int lg[maxn+5],RMQ[LOG+1][maxn+5]; int nxt[maxi][maxn+5],cnt[maxn+5]; pair<int,int> pos[maxn+5][maxi+5]; int who[maxn+5][maxi]; void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[sc[i]]]--]=sc[i]; } void MakeSA(int *s,int n,int m=255){ for (int i=1;i<=n;i++) rk[i]=s[i],sc[i]=i,sc[i+n]=0;Sort(n,m); for (int k=1,p=0;p<n;m=p,k<<=1){ p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i; for (int i=1;i<=n;i++) if (SA[i]>k) sc[++p]=SA[i]-k; Sort(n,m);for (int i=1;i<=n;i++) sc[i]=rk[i];rk[SA[1]]=p=1; for (int i=2;i<=n;i++) rk[SA[i]]=(p+=sc[SA[i-1]]!=sc[SA[i]] || sc[SA[i-1]+k]!=sc[SA[i]+k]); } for (int i=1,k=0;i<=n;i++){ if (k) k--; while (s[i+k]==s[SA[rk[i]-1]+k]) k++; RMQ[0][rk[i]]=k; } for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int j=1;(1<<j)<n;j++) for (int i=2;i+(1<<j)-1<=n;i++) RMQ[j][i]=min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]); } int LCP(int x,int y){ if (x>y) swap(x,y);x++; int k=lg[y-x+1]; return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]); } bool cmp(const int &x,const int &y){ if (x==y) return false; for (int i=1;i<=cnt[x] && i<=cnt[y];i++){ if (pos[x][i].fr==n || pos[y][i].fr==n) return x>y; int Lx=pos[x][i].fr+1,Rx=(i<cnt[x]?pos[x][i+1].fr-1:n),lenx=Rx-Lx+1; int Ly=pos[y][i].fr+1,Ry=(i<cnt[y]?pos[y][i+1].fr-1:n),leny=Ry-Ly+1; int lcp=LCP(rk[Lx],rk[Ly]); if (lcp<lenx && lcp<leny) return who[x][s[Lx+lcp]-'a']<who[y][s[Ly+lcp]-'a']; if (Rx==n || Ry==n) return x>y; if (lenx!=leny) return lenx>leny; } return x>y; } struct fastO{ int si;char buf[1<<16]; fastO() {si=0;} void putc(char ch){ if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } int main(){ scanf("%d%s",&n,s+1); for (int i=1;i<=n;i++) a[i]=i-lst[s[i]-'a'],lst[s[i]-'a']=i; MakeSA(a,n,n); for (int j=0;j<maxi;j++) lst[j]=n+1; for (int i=n;i;i--){ lst[s[i]-'a']=i; for (int j=0;j<maxi;j++) nxt[j][i]=lst[j]; cnt[i]=0; for (int j=0;j<maxi;j++) if (nxt[j][i]<=n) pos[i][++cnt[i]]=mp(nxt[j][i],j); sort(pos[i]+1,pos[i]+1+cnt[i]); for (int j=1;j<=cnt[i];j++) who[i][pos[i][j].sc]=j; } for (int i=1;i<=n;i++) ID[i]=i; sort(ID+1,ID+1+n,cmp); for (int i=1;i<=n;i++) writei(ID[i],i<n?' ':'\n'); return 0; }
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S[l_1,r_1]+\cdots+S[l_i,r_i]$ ，$len_i=r_i-l_i+1$ 。处理出 $T$ 的 $fail$ 数组，对 $S$ 先做一遍KMP，记录 $pre_i$ 表示 $S[1,i]$ 与 $T$ 的最大匹配长度，$cnt_i$ 表示 $S[1,i]$ 与 $T$ 的匹配次数。考虑在这个接起来的串上做KMP，定义 $M_i$ 表示 $U_i$ 与 $T$ 的最大匹配长度（即最大的 $len$ 使得 $U_i$ 末尾 $len$ 个与 $T$ 前 $len$ 个相同）。然后考虑从 $M_{i-1}$ 推到 $M_i$ 。第一种情况：$M_i$ 和 $M_{i-1}$ 无关，则我们需要求出 $S[l_i,r_i]$ 与 $T$ 的最大匹配长度 $len(len\le len_i)$ ，可以通过 $pre_{r_i}$ 跳 $fail$ 树得到。第二种情况：$M_i$ 从 $M_{i-1}$ 接一部分过来，假设保留的长度为 $D$ ，需要满足：$D$ 是 $M_{i-1}$ 的 $fail$ 树祖先，这样才能将 $T$ 平移过来。$T[D+1,D+len_i]=S[l_i,r_i]$ ，即 $LCP(T[D+1,m],S[l_i,n])\ge len_i$ ，可以通过求 $S+T$ 串的后缀数组求出LCP。我们对于每一个 $S[l_i,n]$ ，找出 $[rkL_i,rkR_i]$ 表示和 $S[l_i,n]$ 的 $LCP\ge len_i$ 的区间，那么只要 $T[D+1,m]$ 的 $rank$ 在这个区间内就说明 $T[D+1,D+len_i]$ 可以和 $S[l_i,r_i]$ 匹配。而我们要从 $M_{i-1}$ 的祖先中找出最大的满足的 $D$ ，则 $M_i=D+len_i$ 。考虑用权值主席树，每棵树存 $rank$ 对应的信息，就可以求出 $x$ 到根中 $[rkL_i,rkR_i]$ 中的最大值 $D$ 。在这两种情况中挑个大的就可以得到 $M_i$ ，为了后面处理方便，如果 $M_i=m$ ，则令 $M_i=fail[M_i]$ 。求出 $M_i$ 之后我们考虑如何求出答案。首先为了统一询问，我们把 $[L,R]$ 拆成 $[1,R]$ 减去 $[1,L+m-2]$ 。然后考虑求 $U[1,P]$ 的答案，我们可以先求出整段的 $U_i$ ，然后最后补上不完整的一段。继续考虑KMP的过程，之前已经匹配了 $M_{i-1}$ ，定义 $Solve(M,l,r)$ 表示在 $M$ 的基础上添上了 $S[l,r]$ ，产生的匹配数。类似上面，我们讨论两种情况：第一种情况：没有用到 $M$ ，则匹配数为 $cnt_{r}-cnt_{l+m-2}$ 。第二种情况：用到了 $M$ ，假设用到长度为 $D$ ，需要满足：$D$ 是 $M$ 的祖先。$T[D+1,m]=S[l,l+(m-D)-1]$ ，即 $LCP(T[D+1,m],S[l,n])\ge m-D$ 。$l+(m-D)-1\le r$ ，即 $D\ge m-(r-l+1)$ 。这次条件只和 $D$ 有关，因此我们需要另一个权值主席树，用于数出 $M$ 的祖先中包含 $rank(S[l,n])$ 的个数，可以通过标记永久化和单点查询求出。$M$ 祖先中满足条件的范围也可以通过 $fail$ 树上倍增求出。这两种情况累加起来就是 $Solve(M,l,r)$ ，令 $ans_i$ 表示 $U_i$ 的答案，则 $ans_i=ans_{i-1}+Solve(M_{i-1},l_i,r_i)$ 。最后查询 $U[1,P]$ 就是找到对应的 $ans_i$ ，并加上不完整的一段。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=1e6,maxm=5e5,maxk=5e5,maxl=maxn+maxm,maxt=6e7,LOG=20; int n,m,K,Q,pre[maxn+5],cnt[maxn+5]; int l[maxk+5],r[maxk+5],len[maxk+5],L[maxk+5],R[maxk+5],M[maxk+5]; char s[maxn+5],t[maxm+5],a[maxl+5]; int SA[maxl+5],rk[maxl+5],ha[maxl+5],sc[(maxl<<1)+5]; int lg[maxl+5],RMQ[LOG+1][maxl+5]; int E,lnk[maxm+5],nxt[maxm+5],to[maxm+5]; int fai[maxm+5],ST[LOG+1][maxm+5]; int pl,ro[2][maxm+5],ls[maxt+5],rs[maxt+5],val[maxt+5]; LL pos[maxk+5],ans[maxk+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[1<<16],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } int reads(char *s){ int len=0;char ch=readc(); while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();} while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } struct fastO{ int si;char buf[1<<16]; fastO() {si=0;} void putc(char ch){ if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int min(int x,int y) {return x<y?x:y;} inline int max(int x,int y) {return x>y?x:y;} void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0; for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1]; for (int i=n;i;i--) SA[ha[rk[sc[i]]]--]=sc[i]; } void MakeST(char *s,int n,int m=255){ for (int i=1;i<=n;i++) rk[i]=s[i],sc[i]=i,sc[i+n]=0;Sort(n,m); for (int k=1,p=0;p<n;m=p,k<<=1){ p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i; for (int i=1;i<=n;i++) if (SA[i]>k) sc[++p]=SA[i]-k; Sort(n,m);for (int i=1;i<=n;i++) sc[i]=rk[i];rk[SA[1]]=p=1; for (int i=2;i<=n;i++) rk[SA[i]]=(p+=sc[SA[i-1]]!=sc[SA[i]] || sc[SA[i-1]+k]!=sc[SA[i]+k]); } for (int i=1,k=0;i<=n;i++){ if (k) k--; while (s[i+k]==s[SA[rk[i]-1]+k]) k++; RMQ[0][rk[i]]=k; } for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int j=1;(1<<j)<n;j++) for (int i=2;i+(1<<j)-1<=n;i++) RMQ[j][i]=min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]); } int LCP(int x,int y){ x++;int k=lg[y-x+1]; return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]); } int FindL(int x,int len){ int L=1,R=x-1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) LCP(mid,x)>=len?R=mid-1:L=mid+1; return L; } int FindR(int x,int len){ int L=x+1,R=n+m; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) LCP(x,mid)>=len?L=mid+1:R=mid-1; return R; } inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;} int Build(int L,int R,int k){ int p=++pl;val[p]=k; if (L==R) return p; int mid=L+(R-L>>1); ls[p]=Build(L,mid,k);rs[p]=Build(mid+1,R,k); return p; } int Insert(int p,int pos,int k,int l=1,int r=n+m){ int now=++pl;ls[now]=ls[p];rs[now]=rs[p];val[now]=val[p]; if (l==r) {val[now]=k;return now;} int mid=l+(r-l>>1); pos<=mid?ls[now]=Insert(ls[p],pos,k,l,mid):rs[now]=Insert(rs[p],pos,k,mid+1,r); val[now]=max(val[ls[now]],val[rs[now]]); return now; } int Askmax(int p,int L,int R,int l=1,int r=n+m){ if (L==l && r==R) return val[p]; int mid=l+(r-l>>1); if (R<=mid) return Askmax(ls[p],L,R,l,mid); else if (L>mid) return Askmax(rs[p],L,R,mid+1,r); else return max(Askmax(ls[p],L,mid,l,mid),Askmax(rs[p],mid+1,R,mid+1,r)); } int Update(int p,int L,int R,int l=1,int r=n+m){ int now=++pl;ls[now]=ls[p];rs[now]=rs[p];val[now]=val[p]; if (L==l && r==R) {val[now]++;return now;} int mid=l+(r-l>>1); if (R<=mid) ls[now]=Update(ls[p],L,R,l,mid); else if (L>mid) rs[now]=Update(rs[p],L,R,mid+1,r); else ls[now]=Update(ls[p],L,mid,l,mid),rs[now]=Update(rs[p],mid+1,R,mid+1,r); return now; } int Asksum(int A,int B,int pos,int sum=0,int l=1,int r=n+m){ sum+=val[B]-val[A];if (l==r) return sum; int mid=l+(r-l>>1); return pos<=mid?Asksum(ls[A],ls[B],pos,sum,l,mid):Asksum(rs[A],rs[B],pos,sum,mid+1,r); } void DFS(int x,int pre){ ro[0][x]=Insert(ro[0][pre],rk[x+1+n],x); ro[1][x]=ro[1][pre]; if (x>0) ro[1][x]=Update(ro[1][x],FindL(rk[x+1+n],m-x),FindR(rk[x+1+n],m-x)); for (int j=lnk[x];j;j=nxt[j]) if (to[j]<m) DFS(to[j],x); } int Solve(int M,int l,int r){ if (M+r-l+1<m) return 0; int ans=0; if (r-l+1>=m) ans+=cnt[r]-cnt[l+m-2]; int x=M;for (int j=LOG;~j;j--) if (ST[j][x]>=m-(r-l+1)) x=ST[j][x]; return ans+Asksum(ro[1][fai[x]],ro[1][M],rk[l]); } LL Sum(LL P){ if (!P) return 0; int L=1,R=K; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) P<=pos[mid]?R=mid-1:L=mid+1; if (P==pos[L]) return ans[L]; return ans[L-1]+Solve(M[L-1],l[L],l[L]+P-pos[L-1]-1); } int main(){ n=reads(s);m=reads(t); for (int i=1;i<=n;i++) a[i]=s[i]; for (int i=1;i<=m;i++) a[i+n]=t[i]; MakeST(a,n+m); readi(K);readi(Q); for (int i=1;i<=K;i++){ readi(l[i]);readi(r[i]);len[i]=r[i]-l[i]+1; L[i]=FindL(rk[l[i]],len[i]); R[i]=FindR(rk[l[i]],len[i]); } Add(fai[1],1); for (int i=2,j=0;i<=m;i++){ while (j && t[j+1]!=t[i]) j=fai[j]; j+=(t[j+1]==t[i]); fai[i]=j;Add(fai[i],i); } for (int i=1;i<=m;i++) ST[0][i]=fai[i]; for (int j=1;j<=LOG;j++) for (int i=1;i<=m;i++) ST[j][i]=ST[j-1][ST[j-1][i]]; for (int i=1,j=0;i<=n;i++){ while (j && t[j+1]!=s[i]) j=fai[j]; j+=(t[j+1]==s[i]); pre[i]=j; if (j==m) cnt[i]++,j=fai[j]; } for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; fai[0]=m+1;ro[0][m+1]=Build(1,n+m,-1);ro[1][m+1]=Build(1,n+m,0); DFS(0,m+1); for (int i=1;i<=K;i++){ int MAX=Askmax(ro[0][M[i-1]],L[i],R[i]); int x=pre[r[i]]; for (int j=LOG;~j;j--) if (ST[j][x]>len[i]) x=ST[j][x]; if (x>len[i]) x=fai[x]; M[i]=x;if (~MAX) M[i]=max(M[i],MAX+len[i]); if (M[i]==m) M[i]=fai[M[i]]; } for (int i=1;i<=K;i++){ pos[i]=pos[i-1]+r[i]-l[i]+1; ans[i]=ans[i-1]+Solve(M[i-1],l[i],r[i]); // printf("M[%d]=%d ans[%d]=%lld\n",i,M[i],i,ans[i]); } for (int t=1;t<=Q;t++){ LL x,y;readi(x);readi(y); if (y-x+1<m) {writei(0);continue;} writei(Sum(y)-Sum(x+m-2)); } return 0; }
[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛（7）【Counting Good Arrays】题解
题目概述HDU7217解题报告一个显然的想法：定义 $f_{i,j}$ 表示放了 $i$ 位，第 $i$ 位为 $j$ 的方案数，那么：$$ f_{i,j}=\sum_{d|j}f_{i-1,d} $$由于这题要求二维前缀和，考虑先求一次前缀和：$f_{i,j}$ 表示放了 $i$ 位第 $i$ 位小于等于 $j$ 的方案数，那么：$$ f_{i,j}=\sum_{k=1}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$如果没有那个 $1$ ，我们就只需要用到 $m$ 除法分块中所有的节点，这样就可以把第二位状态降到 $O(\sqrt m)$ 。考虑除了第一次之外都至少 $\times 2$ ，这样至多只会乘 $30$ 次，然后考虑如何统计贡献，其实就是考虑把这些 $\times k$ 的部分放进长度为 $n$ 的序列中，并且规定第一个位置前面的都删掉，其他位置为 $1$ ，最后求一遍前缀积得到要求的数组，这样考虑就能求出长度为 $[1,n]$ 的所有情况。因此稍微改变一下 $f_{i,j}$ 的转移。初值 $f_{1,j}=j$ ，转移：$$ f_{i,j}=\sum_{k=2}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$并且 $i$ 最大只有 $30$ 。不难发现转移 $j$ 的时候也是进行除法分块，因此这个转移的复杂度和杜教筛是一致的，即 $O(m^{3\over 4})$ 。因此复杂度为 $O(30m^{3\over 4})$ ，最后答案为：$$ \sum_{i=1}^{30}{n\choose i}f_{i,m} $$示例程序略有卡常，改了下数组访问顺序就过了。#include<cmath> #include<cstdio> using namespace std; typedef long long LL; const int maxs=31622<<1,MOD=1e9+7,LOG=32; int te,n,m,S;LL f[maxs+5][LOG]; int a[maxs+5],ID[2][maxs+5]; inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} #define P(x) ((x)<=S?ID[0][x]:ID[1][m/(x)]) int main(){ for (scanf("%d",&te);te;te--){ scanf("%d%d",&n,&m); a[0]=0;S=sqrt(m); a[++a[0]]=m;ID[1][1]=a[0]; for (int l=2,r;l<=m;l=r+1){ r=m/(m/l);a[++a[0]]=m/l; a[a[0]]<=S?ID[0][a[a[0]]]=a[0]:ID[1][m/a[a[0]]]=a[0]; } for (int i=1;i<=a[0];i++) f[i][1]=a[i]; for (int j=a[0];j;j--){ for (int i=2;i<LOG;i++) f[j][i]=0; for (int l=2,r;l<=a[j];l=r+1){ r=a[j]/(a[j]/l); int x=P(a[j]/l),len=r-l+1; for (int i=2;i<LOG;i++) f[j][i]=ADD(f[j][i],MUL(len,f[x][i-1])); } } int C=1,ans=0; for (int i=1;i<LOG && i<=n;i++){ C=MUL(C,MUL(n-i+1,Pow(i,MOD-2))); ans=ADD(ans,MUL(C,f[P(m)][i])); } printf("%d\n",ans); } return 0; }
[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛（7）1010【Connectivity of Erdős-Rényi Graph】题解
题目概述HDU7218解题报告这道题看起来和城市规划很像，但是由于要考虑概率，所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率，考虑两个连通块的概率：$$ f_if_j(1-p)^{ij}{i+j\choose i}\to g_{i+j} $$考虑指数型生成函数我们就可以把 ${i+j\choose j}$ 去掉，但是 $f_if_j(1-p)^{ij}\to g_{i+j}$ 我们还是没有办法进行卷积。这时候利用Bluestein算法里面的一个套路：$ij={i+j\choose 2}-{i\choose 2}-{j\choose 2}$ ，就可以把 $ij$ 转化成卷积的形式：$$ {f_{i}\over (1-p)^{i\choose 2}}{f_j\over (1-p)^{j\choose 2}}\to{g_{i+j}\over (1-p)^{i+j\choose 2}} $$令 $f'_i$ 表示处理过之后的概率，$F(x)$ 是 $f'_i$ 的指数型生成函数，那么类似城市规划那道题，$F^i(x)\over i!$ 就是 $i$ 个连通块的概率。令 $g_i$ 表示 $i$ 个点无向图的概率，显然 $g_i=1$ 。令 $g'_i$ 表示处理过之后的 $i$ 个点无向图的概率，$G(x)$ 表示 $g'_i$ 的指数型生成函数，则 $G(x)=e^{F(x)}$ 。所以我们就知道了 $F(x)$ ，考虑枚举块数，统计答案：$$ (1-p)^{n\choose 2}[{x^n\over n!}]\sum_{i=1}^{n}i\cdot {F^i(x)\over i!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]\sum_{i=1}^{n}\cdot {F^i(x)\over (i-1)!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]F(x)\sum_{i=0}^{n}\cdot {F^i(x)\over i!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]F(x)e^{F(x)} $$多项式exp太慢了，为了避免就用 $G(x)$ 代替，那么答案就是 $(1-p)^{n\choose 2}[{x^n\over n!}]G(x)\ln G(x)$ 。另一种做法是考虑容斥，这也是城市规划的另一种做法。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率，$g_i$ 表示 $i$ 个点的概率（ $g_i=1$ ），那么：$$ f_0=0,f_i=1-\sum_{j=0}^{i-1}{i-1\choose j-1}(1-p)^{j(i-j)}f_jg_{i-j} $$即枚举第一个点所在连通块的大小，和上面同理，我们利用Bluestein套路，令 $f'_i={f_i\over (1-p)^{i\choose 2}(i-1)!}$ ，则：$$ f'_i={1\over (1-p)^{i\choose 2}(i-1)!}-\sum_{j=0}^{i-1}f'_jg'_{i-j} $$令 $F_1(x)$ ，$G(x)$ 为 $f',g'$ 对应的生成函数，$H(x)$ 为前面那项的生成函数，则：$$ F_1(x)=H(x)-F_1(x)G(x)\\ F_1(x)={H(x)\over 1+G(x)} $$考虑答案，由于期望可以拆分，我们考虑统计连通块大小为 $i$ 时的贡献，最后求和即可：$$ ans_n=\sum_{i=0}^{n}{n\choose i}(1-p)^{i(n-i)}f_ig_{n-i} $$这个式子也可以用套路处理，卷积一遍就可以求出所有的 $ans_n$ 。示例程序多项式ln#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,maxt=1<<20,MOD=998244353; int te,Q,A,B,P,a[maxn+5]; int pw[maxn+5],INV[maxn+5],fac[maxn+5]; int wn[maxt+5],tem[maxt+5],G[maxt+5],H[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,LL b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} void NTTPre(){ int x=Pow(3,(MOD-1)/maxt); wn[maxt/2]=1; for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x); for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1]; } void Make(int n){ INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]); fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]); } void NTT(int *a,int n,int f){ if (f>0){ for (int k=n>>1;k;k>>=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=a[i+j+k]; a[i+j+k]=MUL(x+MOD-y,wn[k+j]); a[i+j]=ADD(x,y); } } else { for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]); a[i+j+k]=ADD(x,MOD-y); a[i+j]=ADD(a[i+j],y); } for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV); reverse(a+1,a+n); } } void Inte(int *F,int *a,int n,int K){ // F=integral(a) for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K])); for (int i=0;i<K;i++) F[i]=0; } void Deri(int *F,int *a,int n,int K){ // F=a' for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i])); for (int i=n-K+1;i<=n;i++) F[i]=0; } void Inv(int *F,int *a,int n){ // F=1/a if (n==1) {F[0]=Pow(a[0],MOD-2);return;} Inv(F,a,n>>1); for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0; NTT(tem,n<<1,1);NTT(F,n<<1,1); for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i])); NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0; } void Ln(int *F,int *a,int n){ // F=ln(a) static int A[maxt+5],B[maxt+5]; Deri(A,a,n-1,1);for (int i=0;i<n;i++) A[i+n]=0; Inv(B,a,n);NTT(A,n<<1,1);NTT(B,n<<1,1); for (int i=0;i<(n<<1);i++) B[i]=MUL(A[i],B[i]); NTT(B,n<<1,-1);Inte(F,B,n-2,1); } int main(){ Make(maxn);NTTPre(); for (readi(te);te;te--){ readi(Q);readi(A);readi(B);P=MUL(A,Pow(B,MOD-2));P=ADD(1,MOD-P); int inv=Pow(P,MOD-2),N=0; for (int i=1;i<=Q;i++) readi(a[i]),N=max(N,a[i]); int t;for (t=1;t<=N;t<<=1); for (int i=0;i<=N;i++) G[i]=MUL(INV[i],Pow(inv,(LL)i*(i-1)/2)); for (int i=N+1;i<t;i++) G[i]=0; Ln(H,G,t); for (int i=t;i<(t<<1);i++) H[i]=G[i]=0; NTT(G,t<<1,1);NTT(H,t<<1,1); for (int i=0;i<(t<<1);i++) G[i]=MUL(G[i],H[i]); NTT(G,t<<1,-1); for (int i=1;i<=Q;i++){ int val=MUL(fac[a[i]],Pow(P,(LL)a[i]*(a[i]-1)/2)); writei(MUL(G[a[i]],val),i<Q?' ':'\n'); } } return 0; }多项式求逆#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,maxt=1<<20,MOD=998244353; int te,Q,A,B,P,a[maxn+5]; int pw[maxn+5],INV[maxn+5],fac[maxn+5]; int wn[maxt+5],tem[maxt+5],G[maxt+5],H[maxt+5],F[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,LL b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} void NTTPre(){ int x=Pow(3,(MOD-1)/maxt); wn[maxt/2]=1; for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x); for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1]; } void Make(int n){ INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]); fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]); } void NTT(int *a,int n,int f){ if (f>0){ for (int k=n>>1;k;k>>=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=a[i+j+k]; a[i+j+k]=MUL(x+MOD-y,wn[k+j]); a[i+j]=ADD(x,y); } } else { for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]); a[i+j+k]=ADD(x,MOD-y); a[i+j]=ADD(a[i+j],y); } for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV); reverse(a+1,a+n); } } void Inte(int *F,int *a,int n,int K){ // F=integral(a) for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K])); for (int i=0;i<K;i++) F[i]=0; } void Deri(int *F,int *a,int n,int K){ // F=a' for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i])); for (int i=n-K+1;i<=n;i++) F[i]=0; } void Inv(int *F,int *a,int n){ // F=1/a if (n==1) {F[0]=Pow(a[0],MOD-2);return;} Inv(F,a,n>>1); for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0; NTT(tem,n<<1,1);NTT(F,n<<1,1); for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i])); NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0; } int main(){ Make(maxn);NTTPre(); for (readi(te);te;te--){ readi(Q);readi(A);readi(B);P=MUL(A,Pow(B,MOD-2));P=ADD(1,MOD-P); int inv=Pow(P,MOD-2),N=0; for (int i=1;i<=Q;i++) readi(a[i]),N=max(N,a[i]); int t;for (t=1;t<=N;t<<=1); for (int i=1;i<=N;i++) G[i]=MUL(INV[i],Pow(inv,(LL)i*(i-1)/2)); for (int i=1;i<=N;i++) H[i]=MUL(INV[i-1],Pow(inv,(LL)i*(i-1)/2)); G[0]=1;H[0]=0;for (int i=N+1;i<(t<<1);i++) G[i]=H[i]=0; Inv(F,G,t); NTT(F,t<<1,1);NTT(H,t<<1,1); for (int i=0;i<(t<<1);i++) F[i]=MUL(F[i],H[i]); NTT(F,t<<1,-1); G[0]=1;F[0]=0; for (int i=1;i<=N;i++) F[i]=MUL(F[i],MUL(fac[i-1],INV[i])); for (int i=N+1;i<(t<<1);i++) F[i]=0; NTT(F,t<<1,1);NTT(G,t<<1,1); for (int i=0;i<(t<<1);i++) F[i]=MUL(F[i],G[i]); NTT(F,t<<1,-1); for (int i=1;i<=Q;i++){ int val=MUL(fac[a[i]],Pow(P,(LL)a[i]*(a[i]-1)/2)); writei(MUL(F[a[i]],val),i<Q?' ':'\n'); } } return 0; }
[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（8）1013【Shattrath City】题解
题目概述HDU7232解题报告比赛的时候想的是正着做，写完DP式子发现是个看起来很可做的东西，结果实际上不能做，寄掉了。实际上应该倒着做，$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 $[i-n+1,i]$ 位置的方案数，那么最终答案就是 $n^m-\sum_{i=n}^{m}f_i\cdot n^{m-i}$ 。考虑容斥转移（随便放，减去上次放和这次不重叠，减去上次放和这次重叠）：$$ f_i=n^{i-j}n!-\sum_{j=n}^{i-n}f_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}f_j\cdot (i-j)! $$由于 $f_i$ 下标从 $n$ 开始不方便，因此考虑令 $g_i=f_{i+n}$ ，则：$$ g_i=n^i n!-\sum_{j=0}^{i-n}g_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}g_j\cdot (i-j)! $$令 $G(x)$ 为 $g_i$ 的生成函数，令 $A(x)=\sum_{i=0}^{\infty}n^in!\cdot x^i,B(x)=\sum_{i=1}^{n-1}i!\cdot x^i$ ，则：$$ G(x)=A(x)-x^nA(x)G(x)-B(x)G(x)\\ G(x)={A(x)\over 1+x^nA(x)+B(x)} $$多项式求逆就行了。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=200000,maxt=1<<19,MOD=998244353; int te,n,m,fac[maxn+5],ans; int wn[maxt+5],tem[maxt+5],A[maxt+5],B[maxt+5],G[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} void Make(int n) {fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i);} void NTTPre(){ int x=Pow(3,(MOD-1)/maxt); wn[maxt/2]=1; for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x); for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1]; } void NTT(int *a,int n,int f){ if (f>0){ for (int k=n>>1;k;k>>=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=a[i+j+k]; a[i+j+k]=MUL(x+MOD-y,wn[k+j]); a[i+j]=ADD(x,y); } } else { for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]); a[i+j+k]=ADD(x,MOD-y); a[i+j]=ADD(a[i+j],y); } for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV); reverse(a+1,a+n); } } void Inv(int *F,int *a,int n){ // F=1/a if (n==1) {F[0]=Pow(a[0],MOD-2);return;} Inv(F,a,n>>1); for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0; NTT(tem,n<<1,1);NTT(F,n<<1,1); for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i])); NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0; } int main(){ Make(maxn);NTTPre(); for (readi(te);te;te--){ readi(n);readi(m); int K=m-n,t;for (t=1;t<=(K<<1);t<<=1); for (int i=0;i<t;i++) A[i]=B[i]=0; for (int i=0;i<=K;i++) A[i]=MUL(Pow(n,i),fac[n]); B[0]=1;for (int i=n;i<=K;i++) B[i]=A[i-n]; for (int i=1;i<=K && i<n;i++) B[i]=ADD(B[i],fac[i]); Inv(G,B,t>>1); NTT(G,t,1);NTT(A,t,1); for (int i=0;i<t;i++) G[i]=MUL(G[i],A[i]); NTT(G,t,-1); ans=Pow(n,m); for (int i=n;i<=m;i++) ans=ADD(ans,MOD-MUL(G[i-n],Pow(n,m-i))); writei(ans); } return 0; }
[多项式exp]2022“杭电杯”中国大学生算法设计超级联赛（6）1003【Find the Number of Paths】题解
题目概述HDU7199解题报告多项式套路题，需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ，有 $n+k-i$ 条路径，这个形式不太友好，因此我们考虑把整个序列反过来，即 $i$ 点变为 $n+k-i$ 点，这样就变成了 $i\to i-1$ 有 $i$ 条路径，就和下标对应起来了。翻转过后，第二种路径就变成了 $i\to i+x$ 有 $a_x$ 条路径。接下来考虑每轮的转移，定义 $f_{i,j}$ 表示走了 $i$ 步，停在 $j$ 的方案数（初值 $f_{0,n-1}=1$ ），那么：$$ f_{i,j}=(j+1)f_{i-1,j+1}+\sum_{x=1}^{n-1}a_xf_{i-1,k-x}=(j+1)f_{i-1,j+1}+\sum_{k=0}^{j-1}a_{j-k}f_{i-1,k} $$后面是卷积形式，而前面由于我们已经把下标和权值对应了，因此不难发现如果用多项式表示，这是求导的过程。定义 $F_i(x)$ 为 $f_{i}$ 的生成函数，令 $A(x)=\sum_{i=1}^{n-1}a_ix^i$ ，那么：$$ F_i(x)=F_{i-1}'(x)+A(x)F_{i-1}(x) $$这个形式让我们想到构造 $P_i(x)=e^{G(x)}F_i(x)$ ，因为：$$ P_i'(x)=e^{G(x)}G'(x)F_i(x)+e^{G(x)}F_i'(x)=e^{G(x)}[F_i'(x)+G'(x)F_i(x)] $$因此如果让 $G'(x)=A(x),G(x)=\int A(x)dx$ 就可以让后面出现 $F_i'(x)+A(x)F_i(x)$ ，从而：$$ P_i'(x)=e^{G(x)}[F_i'(x)+A(x)F_i(x)]=e^{G(x)}F_{i+1}(x)=P_{i+1}(x) $$这样我们只要求出 $P_0(x)=e^{G(x)}F_0(x)=x^{n-1}e^{G(x)}$ ，然后求 $k$ 阶导就可以得到 $P_k(x)$ ，最后 $F_k(x)={P_k(x)\over e^{G(x)}}$ 。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxt=1<<20,MOD=998244353; int te,n,K,A[maxt+5]; int fac[maxt+5],INV[maxt+5]; int wn[maxt+5],tem[maxt+5],G[maxt+5],P[maxt+5],F[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} void NTTPre(){ int x=Pow(3,(MOD-1)/maxt); wn[maxt/2]=1; for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x); for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1]; } void Make(int n){ INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]); fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]); } void NTT(int *a,int n,int f){ if (f>0){ for (int k=n>>1;k;k>>=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=a[i+j+k]; a[i+j+k]=MUL(x+MOD-y,wn[k+j]); a[i+j]=ADD(x,y); } } else { for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]); a[i+j+k]=ADD(x,MOD-y); a[i+j]=ADD(a[i+j],y); } for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV); reverse(a+1,a+n); } } void Inte(int *F,int *a,int n,int K){ // F=integral(a) for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K])); for (int i=0;i<K;i++) F[i]=0; } void Deri(int *F,int *a,int n,int K){ // F=a' for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i])); for (int i=n-K+1;i<=n;i++) F[i]=0; } void Inv(int *F,int *a,int n){ // F=1/a if (n==1) {F[0]=Pow(a[0],MOD-2);return;} Inv(F,a,n>>1); for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0; NTT(tem,n<<1,1);NTT(F,n<<1,1); for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i])); NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0; } void Ln(int *F,int *a,int n){ // F=ln(a) static int A[maxt+5],B[maxt+5]; Deri(A,a,n-1,1);for (int i=0;i<n;i++) A[i+n]=0; Inv(B,a,n);NTT(A,n<<1,1);NTT(B,n<<1,1); for (int i=0;i<(n<<1);i++) B[i]=MUL(A[i],B[i]); NTT(B,n<<1,-1);Inte(F,B,n-2,1); } void Exp(int *F,int *a,int n){ // F=exp(a) if (n==1) {F[0]=1;return;} Exp(F,a,n>>1);Ln(tem,F,n); for (int i=0;i<n;i++) tem[i]=ADD(a[i],MOD-tem[i]),tem[i+n]=F[i+n]=0;tem[0]=ADD(tem[0],1); NTT(tem,n<<1,1);NTT(F,n<<1,1); for (int i=0;i<(n<<1);i++) tem[i]=MUL(tem[i],F[i]); NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0; } int main(){ NTTPre();Make(maxt); for (readi(te);te;te--){ readi(n);readi(K); int t;for (t=1;t<=n+K-1;t<<=1); A[0]=0;for (int i=1;i<n;i++) readi(A[i]); Inte(A,A,n-1,1);for (int i=n+1;i<t;i++) A[i]=0; Exp(G,A,t); for (int i=n-1;i<=n+K-1;i++) P[i]=G[i-(n-1)]; for (int i=0;i<n-1;i++) P[i]=0; Deri(P,P,n+K-1,K); int s;for (s=1;s<=(n-1<<1);s<<=1); for (int i=n;i<s;i++) P[i]=0; for (int i=t;i<s;i++) G[i]=0; NTT(P,s,1);Inv(F,G,s>>1);NTT(F,s,1); for (int i=0;i<s;i++) F[i]=MUL(F[i],P[i]); NTT(F,s,-1); for (int i=n-1;i>=0;i--) writei(F[i],i>0?' ':'\n'); } return 0; }
[珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛（5）1001【Pandaemonium Asphodelos: The First Circle (Savage)】题解
题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色，所以我们可以考虑用set维护所有的颜色相同的线段，然后每次操作就是对set中的线段进行分裂以及合并，复杂度分析和线段树的分裂与合并是一样的，总共需要分裂或者合并 $O(q)$ 次（在随机数据下，这种做法被称为珂朵莉树，因为随机数据下块数不超过 $\log\log n$ ，虽然和这题没什么关系）。然后对于颜色整体加和单点查询，就利用经典的技巧：维护整体加的tag，然后每次区间 $[L,R]$ 颜色转换时，把更改颜色的贡献区间加到 $[L,R]$ 上，例如 $pos$ 位置从 $c$ 颜色变成了 $d$ 颜色，列出等式 $tag_c+ask(pos)=tag_d+ask'(pos)$ ，得到 $ask'(pos)-ask(pos)=tag_c-tag_d$ ，因此进行 $[L,R]$ 上整体加 $tag_c-tag_d$ 即可。示例程序这个 $1$ 操作说的最近 $2c$ 个点是真的最近 $2c$ 个点……如果顶到头就需要往另一边扩展（玩文字游戏是吧）。#include<set> #include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxq=100000,maxt=2e7; int te,n,Q;LL tag[maxq+5]; struct node{ int L,R,c; node(int l=0,int r=0,int w=0) {L=l;R=r;c=w;} bool operator < (const node &a) const {return L<a.L;} }; typedef set<node>::iterator SI; set<node> S;SI it,l,r; int pl,ro,ls[maxt+5],rs[maxt+5];LL sum[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int newnode() {pl++;ls[pl]=rs[pl]=sum[pl]=0;return pl;} void Insert(int &p,int L,int R,LL k,int l=1,int r=n){ if (!p) p=newnode(); if (L==l && r==R) {sum[p]+=k;return;} int mid=l+(r-l>>1); if (R<=mid) Insert(ls[p],L,R,k,l,mid); else if (L>mid) Insert(rs[p],L,R,k,mid+1,r); else Insert(ls[p],L,mid,k,l,mid),Insert(rs[p],mid+1,R,k,mid+1,r); } LL Ask(int p,int pos,LL now=0,int l=1,int r=n){ if (!p) return now;now+=sum[p]; if (l==r) return now; int mid=l+(r-l>>1); return pos<=mid?Ask(ls[p],pos,now,l,mid):Ask(rs[p],pos,now,mid+1,r); } inline SI Node(int x) {return prev(S.upper_bound(node(x,1e9)));} SI Split(int x){ if (x>n) return S.end(); it=Node(x);if (it->L==x) return it; int L=it->L,R=it->R,c=it->c; S.erase(it);S.insert(node(L,x-1,c)); return S.insert(node(x,R,c)).first; } void Assign(int L,int R,int c){ r=Split(R+1);l=Split(L); for (it=l;it!=S.end() && it->R<=R;it=S.erase(it)) Insert(ro,it->L,it->R,tag[it->c]-tag[c]); S.insert(node(L,R,c)); } void Cover(int x,int y,int c){ int L=max(x-y,1),R=L+y+y; if (R>n) R=n,L=R-y-y; Assign(L,R,c); } void Copy(int x,int y){ l=r=Node(y);int Y=l->c; while (l!=S.begin() && prev(l)->c==Y) l=prev(l); while (next(r)!=S.end() && next(r)->c==Y) r=next(r); Assign(l->L,r->R,Node(x)->c); } int main(){ for (readi(te);te;te--){ readi(n);readi(Q); for (int i=0;i<=Q;i++) tag[i]=0; S.clear();S.insert(node(1,n,0)); pl=ro=0; LL lstans=0; for (int t=1,tp,x,y;t<=Q;t++){ readi(tp);readi(x);x=((x-1)^lstans)%n+1; if (tp==1) readi(y),y=((y-1)^lstans)%((n-1)/2)+1,Cover(x,y,t); else if (tp==2) readi(y),y=((y-1)^lstans)%n+1,Copy(x,y); else if (tp==3) readi(y),tag[Node(x)->c]+=y; else lstans=Ask(ro,x)+tag[Node(x)->c],writei(lstans),lstans&=1073741823; } } return 0; }
[回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解
题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$ 。对于每个节点记录 $sum_p$ 表示 $p$ 在 $fail$ 树上所有祖先的权值和，如果插入一个字符后停在了 $p$ ，那么就会获得 $sum_p$ 的权值。为了防止暴力回退复杂度爆炸，需要记录转移数组。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=500000,maxt=1000000,maxi=26,MOD=1e9+7; int te,N,m,n,pw[maxn+5];char s[maxt+5]; int pl,pb,son[maxt+5][maxi],qui[maxt+5][maxi],len[maxt+5],fai[maxt+5]; int sum[maxt+5],pos[maxt+5],si[maxt+5],who[maxt+5],ans; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;} int reads(char *s){ int len=0;char ch=getlwr(); while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } struct fastO{ int si;char buf[100000]; fastO() {si=0;} inline void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ static int len=0,buf[100]; if (x<0) putchar('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} inline int newnode() {pl++;for (int i=0;i<maxi;i++) son[pl][i]=qui[pl][i]=0;return pl;} inline int val(int p) {return len[p]<=N?MUL(N-len[p]+1,pw[N-len[p]]):0;} void Extend(int i){ int c=s[i]-'a';if (i-len[pb]-1<1 || s[i-len[pb]-1]-'a'!=c) pb=qui[pb][c]; who[i]=pb; if (!son[pb][c]){ int u=newnode(),k=fai[pb];len[u]=len[pb]+2; if (s[i-len[k]-1]-'a'!=c) k=qui[k][c];k=son[k][c]; for (int i=0;i<maxi;i++) qui[u][i]=qui[k][i]; qui[u][s[i-len[k]]-'a']=k;fai[u]=k;son[pb][c]=u; sum[u]=ADD(sum[fai[u]],val(u)); } pb=son[pb][c];ans=ADD(ans,sum[pb]); pos[i]=pb;si[i]=pl; } int main(){ pw[0]=1;for (int i=1;i<=maxn;i++) pw[i]=MUL(pw[i-1],26); for (readi(te);te;te--){ readi(N);readi(m);n=reads(s); pl=-1;newnode();newnode(); fai[0]=fai[1]=1;len[0]=0;len[1]=-1;sum[0]=sum[1]=0; for (int i=0;i<maxi;i++) qui[0][i]=1; pb=0;pos[0]=pb;si[0]=pl; ans=0;for (int i=1;i<=n;i++) Extend(i); writei(ans); for (int t=1,tp;t<=m;t++){ readi(tp); if (tp==2){ ans=ADD(ans,MOD-sum[pos[n]]); if (si[n]>si[n-1]) son[who[n]][s[n]-'a']=0; n--;pb=pos[n];pl=si[n]; } else s[++n]=getlwr(),Extend(n); writei(ans); } } return 0; }
[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点肯定都被包含在了某些点中。假设前一个点为 $(x_1,y_1)$ ，后一个点为 $(x_2,y_2)$ ，那么可以在 $(x_1,y_1)$ 标记 $1$ ，$(x_2,y_1)$ 标记 $-1$ ，最后做一遍二位前缀和，这样就可以避免重复计数。考虑扩展到三维，按照 $x$ 递增的顺序考虑 $(y,z)$ 。对于 $x$ ，如果没有新的 $(y,z)$ ，那么 $x$ 当前的二维局面和 $x-1$ 是一致的，我们可以延续过来。但是如果需要新添加 $(y,z)$ ，在 $(y,z)$ 右上角的点都会被删除。因此考虑用set维护二维局面，当加入和删除点时，由于与上一个局面不同，因此我们需要在这些位置打上 $+1$ 或 $-1$ 标记来修正。最后做一次三维前缀和就可以得到答案。为了方便，建议刚开始向set中添加左上角点 $(0,MAX+1)$ 以及右下角点 $(MAX+1,0)$ 。示例程序#include<set> #include<cstdio> #include<cctype> #include<random> #include<algorithm> #define fr first #define sc second #define mp make_pair #define A first #define B second.first #define C second.second using namespace std; typedef long long LL; const int maxn=1000000,maxq=2000000,maxm=1000000,maxa=400,MOD=998244353; int n,Q,seed,f[maxa+5][maxa+5][maxa+5],ans[maxq+5]; int m;pair<int, pair<int,int> > a[maxm+5]; set< pair<int,int> > S;set< pair<int,int> >::iterator it; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Update(int A,set< pair<int,int> >::iterator it,int x){ f[A][it->fr][it->sc]+=x; f[A][next(it)->fr][it->sc]-=x; } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int main(){ readi(n);readi(Q); for (int i=1;i<=n;i++){ readi(m); for (int i=1;i<=m;i++) readi(a[i].A),readi(a[i].B),readi(a[i].C); sort(a+1,a+1+m); S.clear();S.insert(mp(0,maxa+1));S.insert(mp(maxa+1,0)); for (int i=1;i<=m;i++){ int A=a[i].A;pair<int,int> p=a[i].sc; it=prev(S.upper_bound(p)); if (it->sc<=p.sc) continue; Update(A,it,-1); for (it++;it->sc>=p.sc;it=S.erase(it)) Update(A,it,-1); it=S.insert(p).fr; Update(A,it,1);Update(A,--it,1); } } for (int i=1;i<=maxa;i++) for (int j=1;j<=maxa;j++) for (int k=1;k<=maxa;k++) f[i][j][k]+=f[i-1][j][k]; for (int i=1;i<=maxa;i++) for (int j=1;j<=maxa;j++) for (int k=1;k<=maxa;k++) f[i][j][k]+=f[i][j-1][k]; for (int i=1;i<=maxa;i++) for (int j=1;j<=maxa;j++) for (int k=1;k<=maxa;k++) f[i][j][k]+=f[i][j][k-1]; readi(seed); std::mt19937 rng(seed); std::uniform_int_distribution<> u(1,400); int lastans=0; for (int i=1;i<=Q;i++){ int IQ=(u(rng)^lastans)%400+1; // The IQ of the i-th friend int EQ=(u(rng)^lastans)%400+1; // The EQ of the i-th friend int AQ=(u(rng)^lastans)%400+1; // The AQ of the i-th friend lastans=f[IQ][EQ][AQ]; // The answer to the i-th friend ans[i]=lastans; } seed%=MOD; int pw=1,ha=0; for (int i=Q;i;i--){ ha=ADD(ha,MUL(ans[i],pw)); pw=MUL(pw,seed); } printf("%d\n",ha); return 0; }