Day [-n,-2]天天考试，天天爆炸+被学弟吊打。Day -1在家休息（颓废）了一天，下午去找放学了的同学打了下乒乓球。内心虚的一批，和同学聊了下未来规划发现人家是立志考少年班的人……我这种半吊子水平菜爆了。Day 0早上坐了4h的车到了填镇海，住的酒店就在镇海边上，走几步就到了非常舒服。晚上点外卖，稍微浪了下到了十一点就睡了，睡的并不好（暗示GG）。Day 1早上是……具体数学？下降幂多项式？成功在第二张PPT掉线，于是就去看板子了。下午是杂题（神题）选讲，有点困就直接掉线了，学了下广义SAM，背了下Emacs板子。晚上试机，右边是DYT，他告诉我Linux机房几乎都是学军的QAQ。回去十点就睡了，结果睡的更不好了（暗示GG×2）。Day 2早上是数据结构，之前还能懂一点的，然后到AAA-Tree我就自闭了。不过AAA-Tree之后放了一道法老出过的题，就强行上台冒了一波泡QwQ……中午面基了memset0大佬，初三神仙好巨啊Orz。下午是随机，全程掉线，不过之后放了一道我做过的题，本来想推BZT神仙上去的，结果他不在，反倒是我被学弟推上去了QAQ……晚上教练请客，回去之后慌的很，还是十点就睡了，睡的挺好的但是……Day 3醒来的时候就发现脑子不太清醒（暗示GG×3），但不是特别在意。进了考场才发现我脑子根本不清醒，磕了能量饮料点开题目……九条……可怜？麻……将？？？？？？？？？？？？是的，第一眼就看到了这个：是八木唯！啊我死了！QAQAQAQ！！！T1麻将，字面意思。T2又双叒叕是线段树。T3一脸懵逼。好了一口奶T3不可做，然后我就淦T1去了。总觉得T1 $n\le 13$ 剪剪枝就过了，结果 $n>10$ 我就过不去了。然后就爆炸了，太棒了。预计得分 $20+20+10$ ，没错三题暴力，成功滚粗。出来之后发现全世界T2都会做，全世界T3都会 $50$ 分。各路大佬纷纷表示基准分 $20+40+50$（或更高）。嗯，怎么说呢，我退役了，真棒。UPD：成功 $50$ 分，目前 $100$ 名左右，希望二试能翻盘……
题目概述有一棵 $n$ 个节点的树，每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字符串。求所有本质不同的字符串。叶子节点个数不超过 $20$ 。解题报告ZJOI听课掉线？不如临时抱佛脚！因为所有形成的字符串都是两个叶子节点之间的路径的子串，所以我们可以从每个叶子出发构造一棵Trie，把这些Trie合并成一棵大Trie，然后求这棵大Trie中有多少本质不同的子串。求本质不同的子串可以用SAM，但是树上SAM是什么鬼啊？？？广义SAM，记录下每个点的停留节点，每次加入节点的时候从上一次的停留节点开始，检查待添加节点是否存在，如果存在的话就不需要新建节点，只需要新建辅助节点，否则就正常插入。示例程序#include<cstdio> using namespace std; typedef long long LL; const int maxn=100000,maxt=4000000,maxc=10; int n,m,c[maxn+5],D[maxn+5]; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5]; namespace SAM{ int len=1,ro=1,son[maxt+5][maxc],fa[maxt+5],MAX[maxt+5]; inline int Extend(int p,int c){ if (son[p][c]){ int q=son[p][c];if (MAX[p]+1==MAX[q]) return q; int nq=++len;MAX[nq]=MAX[p]+1;for (int i=0;i<m;i++) son[nq][i]=son[q][i]; fa[nq]=fa[q];fa[q]=nq;while (p&&son[p][c]==q) son[p][c]=nq,p=fa[p];return nq; } else{ int np=++len;MAX[np]=MAX[p]+1;while (p&&!son[p][c]) son[p][c]=np,p=fa[p]; if (!p) return fa[np]=ro,np;int q=son[p][c];if (MAX[p]+1==MAX[q]) return fa[np]=q,np; int nq=++len;MAX[nq]=MAX[p]+1;for (int i=0;i<m;i++) son[nq][i]=son[q][i]; fa[nq]=fa[q];fa[q]=fa[np]=nq;while (p&&son[p][c]==q) son[p][c]=nq,p=fa[p];return np; } } inline LL Count() {LL sum=0;for (int i=1;i<=len;i++) sum+=MAX[i]-MAX[fa[i]];return sum;} } #define Add(x,y) (son[++E]=(y),D[x]++,nxt[E]=lnk[x],lnk[x]=E) void Dfs(int x,int lst,int pre=0){ int now=SAM::Extend(lst,c[x]); for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],now,x); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&c[i]); for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x); for (int i=1;i<=n;i++) if (D[i]==1) Dfs(i,1);printf("%lld\n",SAM::Count());return 0; }
题目概述有一个序列 $\{a_n\}$ ，定义一次操作 $[L,R]$ 表示将 $[L,R]$ 中的数改成 $[L,R]$ 中的最大数。现在要进行 $q$ 轮，每轮随机一个区间 $[L,R]$ 进行操作，求出每个位置上最后数的期望。解题报告神仙DP题，我只会 $O(n^53^nq)$ ，加上玄学优化只能过 $n=8$ ……根据期望的线性性，我们可以枚举 $i,j$ 表示 $i$ 这个位置最后变成第 $j$ 小的数的方案数，然后贡献就是方案数乘上 $a_j$ 。于是会想到这样的状态 $f_{i,x,L,R}$ 表示第 $i$ 轮 $[L,R]$ 变成第 $x$ 小的数的方案数，但是很明显这样无法存下所有状态，而且还会重复，所以是假的。Orz劼司机，我们可以简单容斥一下：求出 $\le j​$ 的答案，那么减去 $\le j-1​$ 的答案就是 $=j​$ 的答案，所以我们可以定义 $f_{i,x,L,R}​$ 表示第 $i​$ 轮 $[L,R]​$ 变成 $\le​$ 第 $x​$ 小的数的方案数，同时 $L-1​$ 和 $R+1​$ 均 $>​$ 第 $x​$ 小的数，这样状态就是唯一的，并且隔开了外界，就可以转移了。转移有三种：这次操作不影响 $[L,R]$ ，即要么在外面操作，要么在内部操作：$f_{i,x,L,R}\leftarrow f_{i-1,x,L,R}({(L-1)L\over 2}+{(R-L+1)(R-L+2)\over 2}+{(n-R)(n-R+1)\over 2})$枚举上一次的状态 $[l,R],l<L$ ，那么可以通过操作左端点在 $[1,l-1]$ ，右端点在 $L-1$ 来转移：$f_{i,x,L,R}\leftarrow f_{i-1,x,l,R}(l-1)$枚举上一次的状态 $[L,r],r>R$ ，那么可以通过操作左端点在 $R+1$ ，右端点在 $[r+1,n]$ 来转移：$f_{i,x,L,R}\leftarrow f_{i-1,x,L,r}(n-r)$然后定义 $g_{i,j}$ 表示 $i$ 这个位置变成 $\le$ 第 $j$ 小的数的方案数，则：$g_{i,j}\leftarrow f_{q,j,L,R}(i\in[L,R])$ 。考虑初始状态，我们枚举 $i$ 表示这次最大的数，然后往左往右找到 $i$ 的控制区间 $[L,R]$ ，做这个区间的DP。我们发现后面两个转移都可以前缀和优化，所以这样是 $O(n^3q)$ 的……爆炸了？！不过数是随机的……所以跑不满，可以过……最后要注意到 $g_{i,j}$ 是不连续的，所以不能用 $g_{i,j}-g_{i,j-1}$ 来算，要记录上一次存在的 $g_{i,j}$ 。示例程序#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=400,MOD=1e9+7; int n,m,ID[maxn+5],a[maxn+5],rk[maxn+5],s[maxn+5][maxn]; LL f[2][maxn+5][maxn+5],g[maxn+5][maxn+5]; inline bool cmp(const int &A,const int &B) {return a[A]<a[B];} #define Seg(x) ((LL)(x)*((x)+1)>>1) inline void Solve(int L,int R,int rk){ for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) f[0][i][j]=0; for (int t=f[0][L][R]=1,c=1;t<=m;t++,c^=1){ LL (*F)[maxn+5]=f[c],(*G)[maxn+5]=f[c^1],sum; for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) F[i][j]=G[i][j]*s[i][j]; for (int j=(sum=0,L);j<=R;j++,sum=0) for (int i=L;i<=j;i++) F[i][j]+=sum,sum+=G[i][j]*(i-1); for (int i=(sum=0,L);i<=R;i++,sum=0) for (int j=R;j>=i;j--) F[i][j]+=sum,sum+=G[i][j]*(n-j); for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) F[i][j]%=MOD; } for (int i=L;i<=R;i++) for (int j=L;j<=i;j++) for (int k=i;k<=R;k++) g[i][rk]=(g[i][rk]+f[m&1][j][k])%MOD; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),ID[i]=i; a[0]=a[n+1]=2e9;sort(ID+1,ID+1+n,cmp);for (int i=1;i<=n;i++) rk[ID[i]]=i; for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) s[i][j]=(Seg(i-1)+Seg(j-i+1)+Seg(n-j))%MOD; for (int i=1,L,R;i<=n;i++) {for (L=i;a[L-1]<=a[i];L--);for (R=i;a[R+1]<=a[i];R++);Solve(L,R,rk[i]);} for (int i=1,ans=0;i<=n;i++,ans=0){ for (int j=1,lst=0;j<=n;j++) if (g[i][j]) ans=(ans+(LL)(g[i][j]+MOD-lst)*a[ID[j]]%MOD)%MOD,lst=g[i][j]; printf("%d",ans);i<n?putchar(' '):puts(""); }return 0; }
题目概述有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的距离。解题报告很明显只需要在最终树上询问就行了，然后区间修改太变态了，我们用离线+扫描线来维护每棵树的LCT。考虑怎么维护加点和改根这两个操作，加点可以直接找到父亲和儿子插进去，但是改根操作会引起大量信息改动导致爆炸，所以我就不会了……LCT建辅助点太神仙了……对于每个改根操作，我们都建一个辅助点（辅助点没有点权），然后对于每个加点操作，我们都连向最近的改根操作，每个改根操作也连向上一个改根操作。一旦改根了，我们就把这个改根操作和上一个改根操作断开，连向改成的根节点，这样就完成了大量的信息改动。但是这样连边有个小问题，就是询问 $x,y$ 的时候，$x,y$ 可能会经过辅助点而不是经过了实际的点，导致统计出错，所以我们需要把点权改成边权，只有加点（实点指向辅助点）的时候才有边权，否则没有边权，这样就没有问题了。最后还有一个很恶心的事情，就是换根操作可能无效。不过由于加点是连续的，所以我们对于每个换根操作，将操作的区间和根节点存在的区间取并，就可以保证换根操作都是有效的。示例程序#include<cstdio> #include<cctype> #include<vector> #include<algorithm> #define pb push_back using namespace std; const int maxn=100000,maxm=200000,maxt=maxm*3; int n,m,ID[maxm+5];struct data {int tp,A,B,C;} q[maxm+5]; int son[maxt+5][2],fa[maxt+5],si[maxt+5];bool ex[maxt+5],flip[maxt+5]; int pre[maxm+5],ans[maxm+5];vector<int> A[maxn+5],B[maxn+5],C[maxn+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> inline 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(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void getdata(data &a) {readi(a.tp);readi(a.A);readi(a.B);if (a.tp) readi(a.C);} #define is_ro(p) (son[fa[p]][0]!=(p)&&son[fa[p]][1]!=(p)) #define Son(p) (son[fa[p]][1]==(p)) inline void Pushup(int p) {si[p]=si[son[p][0]]+ex[p]+si[son[p][1]];} inline void Rotate(int t){ int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p; if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t); if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t; } inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;} inline void Pushdown(int p) {if (flip[p]) flip[p]^=1,Addflip(son[p][0]),Addflip(son[p][1]);} inline void Splay(int p){ static int stk[maxn+5],top;stk[top=1]=p; for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i]; while (top) Pushdown(stk[top--]); for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p]) if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p); } inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);} inline void Makero(int x) {Access(x);Splay(x);Addflip(x);} inline void Link(int x,int y) {Makero(x);Makero(y);fa[y]=x;} inline void Cut(int x,int y) {Makero(x);Access(y);Splay(x);son[x][1]=fa[y]=0;Pushup(x);} inline int Ask(int x,int y) {Makero(x);Access(y);Splay(y);return si[y];} inline void Update(int x,int f) {Splay(x);ex[x]=f;Pushup(x);} int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(m);m++;for (int i=2;i<=m;i++) getdata(q[i]);Link(1,(m<<1)+1);Link((m<<1)+1,m+1); for (int i=2,now=1,lst=1;i<=m;i++) if (q[i].tp==2) C[q[i].A].pb(i); else{ if (!q[i].tp) ID[q[i].C=++now]=i,Update((m<<1)+now,1); else{ int now=ID[q[i].C];if (now) q[i].A=max(q[i].A,q[now].A),q[i].B=min(q[i].B,q[now].B); if (q[i].A<=q[i].B) Link(m+lst,m+i); }pre[i]=lst;if (q[i].A<=q[i].B) A[q[i].A].pb(i),B[q[i].B+1].pb(i),q[i].tp?lst=i:0; } for (int i=1;i<=n;i++){ for (int j=0,si=B[i].size(),u;j<si;j++) if (q[u=B[i][j]].tp) Cut(q[u].C,m+u),Link(m+pre[u],m+u); else Cut(q[u].C,(m<<1)+q[u].C),Cut((m<<1)+q[u].C,m+pre[u]); for (int j=0,si=A[i].size(),u;j<si;j++) if (q[u=A[i][j]].tp) Cut(m+pre[u],m+u),Link(q[u].C,m+u); else Link(q[u].C,(m<<1)+q[u].C),Link((m<<1)+q[u].C,m+pre[u]); for (int j=0,si=C[i].size(),u;j<si;j++) u=C[i][j],ans[u]=Ask(q[u].B,q[u].C); }for (int i=1;i<=m;i++) if (q[i].tp==2) printf("%d\n",ans[i]);return 0; }
题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪，但是三个妹子之间不能有冲突，一种方案 $(i,j,k),i<j<k$ 的贡献为：$Ai+Bj+Ck$ ，求所有合法方案的总贡献。解题报告很明显可以容斥：至少 $0$ 个冲突 $-$ 至少 $1$ 个冲突 $+$ 至少 $2$ 个冲突 $-$ 至少 $3$ 个冲突。前面三个都很好算（就是比较烦QAQ），问题是怎么求 $3$ 个冲突的贡献，我们发现 $3$ 个冲突就是个三元环，所以只需要找三元环就行了，可以参考这篇Blog。示例程序#include<cstdio> #include<cctype> #include<vector> #include<algorithm> #define fr first #define sc second #define pb push_back using namespace std; typedef unsigned long long ULL; const int maxn=200000,maxm=200000; int n,m,D[maxn+5];ULL A,B,C,ans;pair<int,int> e[maxm+5]; vector<int> pre[maxn+5],suf[maxn+5];vector<ULL> sum[maxn+5]; int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5],ti,vis[maxn+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> inline 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(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) inline ULL C2(ULL n) {return n*(n-1)>>1;} inline ULL Sum(ULL L,ULL R) {return (L+R)*(R-L+1)>>1;} int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(m);readi(A);readi(B);readi(C); for (int i=1;i<=m;i++) {readi(e[i].fr);readi(e[i].sc);if (e[i].fr>e[i].sc) swap(e[i].fr,e[i].sc);} sort(e+1,e+1+m);m=unique(e+1,e+1+m)-e-1; for (int i=1;i<=m;i++) suf[e[i].fr].pb(e[i].sc); for (int i=1;i<=m;i++) swap(e[i].fr,e[i].sc);sort(e+1,e+1+m); for (int i=1;i<=m;i++) pre[e[i].fr].pb(e[i].sc); for (int i=1;i<=m;i++) D[e[i].fr]++,D[e[i].sc]++; for (int i=1;i<=m;i++) D[e[i].fr]<D[e[i].sc]?Add(e[i].fr,e[i].sc):Add(e[i].sc,e[i].fr); for (int i=0;i<n-2;i++) ans+=A*i*C2(n-i-1); for (int i=1;i<n-1;i++) ans+=B*i*i*(n-i-1); for (int i=2;i<n;i++) ans+=C*i*C2(i); for (int i=0;i<n;i++) for (int j=0,si=suf[i].size();j<si;j++){ int u=suf[i][j]; ans-=(A*i+B*u)*(n-1-u)+C*Sum(u+1,n-1); ans-=(A*i+C*u)*(u-i-1)+B*Sum(i+1,u-1); ans-=(B*i+C*u)*i+A*Sum(0,i-1); } for (int i=0;i<n;i++){ int si=suf[i].size();sum[i].resize(si);if (si) sum[i][0]=suf[i][0]; for (int j=1;j<si;j++) sum[i][j]=sum[i][j-1]+suf[i][j]; } for (int i=0;i<n;i++) for (int j=0,si=suf[i].size();j<si;j++){ int u=suf[i][j]; ans+=(A*i+B*u)*(si-j-1)+C*(sum[i][si-1]-sum[i][j]); if (suf[u].size()) ans+=(A*i+B*u)*suf[u].size()+C*sum[u][suf[u].size()-1]; } for (ULL i=0,sum=0;i<n;i++,sum=0) for (int j=0,si=pre[i].size();j<si;j++) {int u=pre[i][j];ans+=(B*u+C*i)*j+A*sum;sum+=pre[i][j];} for (int i=1;i<=m;i++){ int x=e[i].fr,y=e[i].sc;ti++; for (int j=lnk[x];j;j=nxt[j]) vis[son[j]]=ti; for (int j=lnk[y];j;j=nxt[j]) if (vis[son[j]]==ti){ int a=x,b=y,c=son[j];if (a>b) swap(a,b);if (a>c) swap(a,c);if (b>c) swap(b,c); ans-=A*a+B*b+C*c; } }printf("%llu\n",ans);return 0; }
题目概述用 $K$ 种颜色对 $n\times m$ 的网格进行染色，需要保证无论怎么样纵切将棋盘分为左右两个部分， 两个部分的颜色种类数都必须相等，求方案数。解题报告在NOIP前，这道题被法老当做NOIP题出进了模拟赛……考虑第一列有 $a$ 种颜色，那么 $[2,m]$ 列也有 $a$ 种颜色，再考虑前两列有 $x(x\ge a)$ 种颜色，那么 $[3,m]$ 列也有 $x(x\le a)$ 种颜色，所以 $x=a$ ，以此类推所有格子只有 $a$ 种颜色，反过来考虑同理。因此我们可以枚举 $a$ 表示第一列和第 $n$ 列有 $a$ 种颜色，那么中间 $m-2$ 列只能使用第一列和第 $n$ 列颜色的交集，假设有 $b$ 种颜色，则方案数为：$$ \sum_{a=1}^{min\{n,K\}}\sum_{b=0}^{a}{K\choose a}{K-a\choose a-b}{a\choose b}b^{n(m-2)}[S(n,a)a!]^2 $$前面一堆就表示选出 $a$ 种颜色，$b$ 种交集，中间用 $b$ 种颜色的方案数，后面那个 $S(n,a)$ 表示第二类斯特林数，$[S(n,a)a!]^2$ 表示第一列和第 $n$ 列涂上 $a$ 种颜色的方案数。示例程序#include<cstdio> using namespace std; typedef long long LL; const int maxn=1000,maxk=1000000,MOD=1000000007; int te,n,m,K,fac[maxk+5],INV[maxk+5],S[maxn+5][maxn+5],ans; inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} #define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD) int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); INV[0]=INV[1]=1;for (int i=2;i<=maxk;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD; fac[0]=1;for (int i=1;i<=maxk;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD; S[0][0]=1;for (int i=1;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=(S[i-1][j-1]+(LL)S[i-1][j]*j%MOD)%MOD; for (int i=0;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=Pow((LL)S[i][j]*fac[j]%MOD,2); for (scanf("%d",&te);te;te--){ scanf("%d%d%d",&n,&m,&K);ans=0;if (m==1) {printf("%d\n",Pow(K,n));continue;} for (int i=1;i<=n&&i<=K;i++) for (int j=0;j<=i;j++) ans=(ans+(LL)C(K,i)*C(K-i,i-j)%MOD*C(i,j)%MOD*Pow(j,n*(m-2))%MOD*S[n][i]%MOD)%MOD; printf("%d\n",ans); }return 0; }
题目概述定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列，有些位置还没有确定，求相似度为 $i,i\in[0,n-1)$ 的可能方案数。解题报告这是神仙题。首先假设没有 $0$ ，那么从 $a_i$ 向 $b_i$ 连边，不难发现交换一定发生在循环内，所以相似度即 $n-$循环数。然后考虑 $0$ ，通过缩路径，我们可以把边分成 $0\to 0,0\to B,A\to 0,A\to B$ 以及自带的循环。显然自带的循环以及 $A\to B$ 都不需要考虑，所以我们只要关注 $0\to 0,0\to B,A\to 0$ 这三种，假设分别有 $S_0,S_1,S_2$ 条。由于已经缩过路径，所以 $0\to B,A\to 0$ 想要成环，只能借助 $0\to 0$ 边，因此我们可以先让 $0\to B,A\to 0$ 在内部先分别成环，然后最后再用 $0\to 0$ 去拼接 $0\to B,A\to 0$（以及 $A\to B$ ）。也就是说我们要计算 $F_i(G_i)$ 表示 $0\to B(0\to A)$ 在内部组成恰好 $i$ 个环的方案数，直接算很难算，我们可以考虑广义容斥，先求出 $f_i$ 表示至少 $i$ 个环的方案数，然后容斥求出 $F$（ $G$ 同理）：$$ f_i=\sum_{j=i}^{S_1}{S_1\choose j}s(j,i)(S_0+S_1-j)^{\underline{S_1-j}} $$其中 $s(n,m)$ 为第一类斯特林数，即先钦点 $j$ 条 $0\to B$ 出来组成 $i$ 个环，方案数为 $s(j,i)$ ，剩下的 $n-j$ 条边可以成自环，也可以连向另外的 $0\to B$ ，还可以连向 $0\to 0$ ，反正需要找到一个地方接上去。由于 $F,G$ 各自成环互不相干，所以可以直接 $F*G$ 得到 $i$ 个环的方案数。此时还剩下一些 $0\to B,A\to 0,A\to B$ 的边，我们可以用 $0\to 0$ 将他们连起来，感性理解一下（我不会证明QAQ），决定这些边成环数量的是 $0\to 0$ 的成环数量，而 $S_0$ 条 $0\to 0$ 成 $i$ 个环的方案数就是 $s(S_0,i)S_0!$ ，所以再用这个卷上 $F*G$ ，就可以得到答案了。示例程序#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=2000,MOD=998244353; int n,a[maxn+5],b[maxn+5],S[3],son[maxn+5],cir;bool vis[maxn+5]; int C[maxn+5][maxn+5],fac[maxn+5],A[maxn+5][maxn+5],s[maxn+5][maxn+5]; int f[maxn+5],g[maxn+5],F[maxn+5],G[maxn+5],H[maxn+5],tem[maxn+5],ans[maxn+5]; inline void Make(int n){ fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD; for (int i=s[0][0]=C[0][0]=A[0][0]=1;i<=n;i++) for (int j=C[i][0]=A[i][0]=1;j<=i;j++){ s[i][j]=(s[i-1][j-1]+(LL)s[i-1][j]*(i-1)%MOD)%MOD; C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; A[i][j]=(LL)C[i][j]*fac[j]%MOD; } } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d",&n);Make(n); for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) scanf("%d",&b[i]); for (int i=1;i<=n;i++) son[i]=-1;for (int i=1;i<=n;i++) if (a[i]) son[a[i]]=b[i]; for (int i=1;i<=n;i++) if (!a[i]){ int x=b[i];while (x&&~son[x]) vis[x]=true,x=son[x]; if (!x) S[0]++; else vis[x]=true,S[1]++; } for (int i=1;i<=n;i++) if (a[i]&&!vis[a[i]]){ vis[a[i]]=true;int x=b[i];while (x&&~son[x]&&!vis[x]) vis[x]=true,x=son[x]; if (!x) S[2]++; else if (x==a[i]) cir++; else vis[x]=true; } for (int i=0;i<=S[1];i++) for (int j=i;j<=S[1];j++) f[i]=(f[i]+(LL)C[S[1]][j]*s[j][i]%MOD*A[S[0]+S[1]-j][S[1]-j])%MOD; for (int i=0;i<=S[2];i++) for (int j=i;j<=S[2];j++) g[i]=(g[i]+(LL)C[S[2]][j]*s[j][i]%MOD*A[S[0]+S[2]-j][S[2]-j])%MOD; for (int i=0;i<=S[1];i++) for (int j=i;j<=S[1];j++) F[i]=(F[i]+(LL)(j-i&1?MOD-1:1)*C[j][i]%MOD*f[j]%MOD)%MOD; for (int i=0;i<=S[2];i++) for (int j=i;j<=S[2];j++) G[i]=(G[i]+(LL)(j-i&1?MOD-1:1)*C[j][i]%MOD*g[j]%MOD)%MOD; for (int i=0;i<=S[0];i++) H[i]=(LL)s[S[0]][i]*fac[S[0]]%MOD; for (int i=0;i<=n;i++) for (int j=0;i+j<=n;j++) tem[i+j]=(tem[i+j]+(LL)F[i]*G[j]%MOD)%MOD; for (int i=0;i<=n;i++) for (int j=0;i+j<=n;j++) ans[i+j]=(ans[i+j]+(LL)tem[i]*H[j]%MOD)%MOD; for (int i=0;i<n;i++) n-i-cir<0?putchar('0'):printf("%d",ans[n-i-cir]),i<n-1?putchar(' '):puts(""); return 0; }
题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告就是这题套个NTT，水博客真开心。可能略有卡常……示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=100000,maxt=1<<18,MOD=998244353; int n,INV[maxn+5],a[maxt+5],c[maxt+5];LL K; int rev[maxt+5],pw[2][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> inline 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(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void writei(int x){ static int buf[30],len=0;do buf[len++]=x%10,x/=10; while (x); while (len) putchar(buf[--len]+48); } inline void Make(int n){ INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD; c[0]=1;for (int i=1;i<=n;i++) c[i]=(K-1+i)%MOD*INV[i]%MOD*c[i-1]%MOD; } inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} inline void Pre(int n){ for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1)); for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2); } inline void NTT(int *a,int n,int f){ for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int k=1;k<n;k<<=1){ int gn=pw[f<0][k<<1],g=1,x,y; for (int i=0;i<n;i+=k<<1,g=1) for (int j=0;j<k;j++,g=(LL)g*gn%MOD) x=a[i+j],y=(LL)a[i+j+k]*g%MOD,a[i+j]=(x+y)%MOD,a[i+j+k]=(x+MOD-y)%MOD; }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(K);Make(n);for (int i=0;i<n;i++) readi(a[i]); int t;for (t=1;t<(n<<1);t<<=1);Pre(t);NTT(a,t,1);NTT(c,t,1); for (int i=0;i<t;i++) a[i]=(LL)a[i]*c[i]%MOD;NTT(a,t,-1); for (int i=0;i<n;i++) writei(a[i]),puts("");return 0; }
题目概述有 $n$ 个点的有根树，每个节点只能往上走，且每个节点有一个特产。现在有 $q$ 个询问，每次询问 $c$ 个点，求这些点走到他们的公共祖先，在满足：1.每个人带的特产数量相等。2.没有特产重复出现。的情况下能带的最多的特产数量。解题报告首先我们可以利用bitset+树链剖分+线段树得出一条线段上的特产集合，我们要做的是分配特产使得每个人带的特产尽量多（因为每个人必须带相同数量）。由于是分配问题，我们可以考虑网络流或二分图匹配，假如答案为 $x$ ，那么可以将每个人拆为 $x$ 个点，一个人可以向特产集合中的特产连边，根据霍尔定理，设 $A(S)$ 表示 $S$ 这些人连出去的特产集合，那么 $|A(S)|\ge|S|x$ 。因此 $x=min\{\lfloor{|A(S)|\over |S|}\rfloor\}$ ，答案为 $cx$ 。示例程序#include<cstdio> #include<cctype> #include<bitset> #include<algorithm> using namespace std; const int maxn=300000,maxm=1000,maxk=5,Log=19; int n,m,te,dep[maxn+5],si[maxn+5],ST[maxn+5][Log+5],a[maxn+5]; int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5],SH[maxn+5],top[maxn+5],Lt[maxn+5],who[maxn+5]; int cnt[1<<maxk],H[1<<maxk];bitset<maxm> pre[maxn+5],s[(maxn<<2)+5],now,t[maxk+5],S[1<<maxk]; #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> inline 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(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) void Dfs(int x,int pre=0){ dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];si[x]=1;SH[x]=0; for (int j=lnk[x],u;j;j=nxt[j]) Dfs(u=son[j],x),si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0; } void HLD(int x,int lst){ who[Lt[x]=++Lt[0]]=x;top[x]=lst;if (SH[x]) HLD(SH[x],lst); for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=SH[x]) HLD(son[j],son[j]); } void Build(int L,int R,int p=1){ if (L==R) {s[p][a[who[L]]]=1;return;}int mid=L+(R-L>>1); Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);s[p]=s[p<<1]|s[p<<1|1]; } inline int LCA(int x,int y){ if (dep[x]<dep[y]) swap(x,y);for (int j=Log;~j&&dep[x]>dep[y];j--) if (dep[ST[x][j =dep[y]) x=ST[x][j]; if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0]; } bitset<maxm> Ask(int L,int R,int l=1,int r=n,int p=1){ if (L==l&&r==R) return s[p];int mid=l+(r-l>>1); if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1); else return Ask(L,mid,l,mid,p<<1)|Ask(mid+1,R,mid+1,r,p<<1|1); } inline bitset<maxm> Query(int x,int y){ static bitset<maxm> now;now=0; while (top[x]!=top[y]) {if (dep[x]<dep[y]) swap(x,y);now|=pre[x];x=ST[top[x]][0];} if (Lt[x]>Lt[y]) swap(x,y);now|=Ask(Lt[x],Lt[y]);return now; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(m);readi(te);for (int i=2,fa;i<=n;i++) readi(fa),Add(fa,i); for (int i=1;i<=n;i++) readi(a[i]),a[i]--;Dfs(1);HLD(1,1);Build(1,n); for (int i=1;i<=n;i++) pre[i]=Ask(Lt[top[i]],Lt[i]); H[0]=-1;for (int i=1;i<(1<<maxk);i++) cnt[i]=cnt[i>>1]+(i&1),H[i]=H[i>>1]+1; for (int K,c[maxk+5],ans;te;te--){ readi(K);for (int i=0;i<K;i++) readi(c[i]);ans=2e9; int lca=c[0];for (int i=1;i<K;i++) lca=LCA(lca,c[i]); for (int i=0;i<K;i++) t[i]=Query(c[i],lca); for (int i=1;i<(1<<K);i++) S[i]=S[i^(1<<H[i])]|t[H[i]]; for (int i=1;i<(1<<K);i++) ans=min(ans,(int)S[i].count()/cnt[i]);printf("%d\n",ans*K); }return 0; }
题目概述给出一个操作串：如果是小写字母，表示在当前字符串后面添加这个小写字母。如果是 $−$ ，表示删除当前字符串最后的小写字母（保证合法）。求每次操作后当前字符串不同子串的个数。解题报告暴力后缀自动机回滚做法戳这里。后缀平衡树就是每次前端插入字符（插入一个后缀），动态维护后缀数组（以及rank和height）。有两种写法：1.Hash大法好。2.手写平衡树动态标号。我懒死了当然就直接set+hash啦。具体就是用set维护后缀数组，用二分+Hash定义一下后缀的优先级，然后每次前端插入（其实当成后端插入就行，就是Hash比较的时候需要倒过来）就直接insert(n)就好啦。至于本质不同子串个数，我们插入和删除的时候找到前驱和后继，修正一下Height就行了。set+hash的缺点：1.插入删除复杂度 $O(log_2^2n)$ 。2.没法维护rank数组……求rank可能还是得手写平衡树。示例程序#include<set> #include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL;typedef unsigned long long ULL; const int maxn=100000,BA=19260817; int n;LL ans;char s[maxn+5];ULL pw[maxn+5],ha[maxn+5]; struct SF {int x;SF(int X=0) {x=X;}}; #define Hash(L,R) (ha[R]-ha[(L)-1]*pw[(R)-(L)+1]) inline bool operator < (const SF &a,const SF &b){ int A=a.x,B=b.x,L=1,R=min(A,B);if (Hash(A-R+1,A)==Hash(B-R+1,B)) return A<B; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) Hash(A-mid+1,A)==Hash(B-mid+1,B)?L=mid+1:R=mid-1;return s[A-R]<s[B-R]; } set<SF> S;set<SF>::iterator pre,suf; inline int Height(int A,int B){ int L=1,R=min(A,B); for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) Hash(A-mid+1,A)==Hash(B-mid+1,B)?L=mid+1:R=mid-1;return B-R; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); pw[0]=1;for (int i=1;i<=maxn;i++) pw[i]=pw[i-1]*BA; for (char ch=getchar();islower(ch)||ch=='-';ch=getchar()){ if (islower(ch)){ s[++n]=ch;ha[n]=ha[n-1]*BA+ch-'a';suf=S.upper_bound(SF(n)); if (suf!=S.end()) {if (suf==S.begin()) ans-=(*suf).x;ans+=Height(n,(*suf).x);} if (suf!=S.begin()) pre=suf,pre--,ans+=Height((*pre).x,n); else ans+=n; if (suf!=S.begin()&&suf!=S.end()) ans-=Height((*pre).x,(*suf).x); S.insert(SF(n)); } else{ S.erase(SF(n));if (n==1) ans=0;suf=S.upper_bound(SF(n)); if (suf!=S.end()) {if (suf==S.begin()) ans+=(*suf).x;ans-=Height(n,(*suf).x);} if (suf!=S.begin()) pre=suf,pre--,ans-=Height((*pre).x,n); else ans-=n; if (suf!=S.begin()&&suf!=S.end()) ans+=Height((*pre).x,(*suf).x); n--; }printf("%lld\n",ans); }return 0; }