【考试总结】2022-07-04
字符串
如果某个 \(S\) 的子串 \(S[l\dots r]\) 恰为 \(S[1\dots x]+S[n-y+1\dots n]\) ，那么 \(S[1\dots l+x-1]\) 的 \(\rm Border\) 集合包含 \(x\)，对于后缀同理
正反做两遍 \(\rm KMP\) ，每个点和其 \(\rm nxt\) 连边形成两棵树，此时询问变成了正向树 \(x\) 的子树中有几个点 \(u\) 满足反向树 \(n-y+1\) 号节点的子树里面有 \(u+1\)
这是二维数点问题，可以使用可持久化线段树解决
Code Display
const int N=200010,M=N*40;
char s[N];
int rt[N],ls[M],rs[M],tot,cnt[M];
inline void insert(int &p,int pre,int l,int r,int pos){
p=++tot; ls[p]=ls[pre]; rs[p]=rs[pre]; cnt[p]=cnt[pre]+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) insert(ls[p],ls[pre],l,mid,pos);
else insert(rs[p],rs[pre],mid+1,r,pos);
}
inline int query(int u,int v,int l,int r,int st,int ed){
if(!u) return 0;
if(st<=l&&r<=ed) return cnt[u]-cnt[v];
int mid=(l+r)>>1,res=0;
if(st<=mid) res+=query(ls[u],ls[v],l,mid,st,ed);
if(ed>mid) res+=query(rs[u],rs[v],mid+1,r,st,ed);
return res;
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int T=read();
while(T--){
tot=0;
int n=read(),Q=read();
scanf("%s",s+1);
vector >Gp(n+2),Gs(n+2);
vector prenxt(n+2),sufnxt(n+2);
vector inp(n+2),ins(n+2),outp(n+2),outs(n+2);
vector val(n+2);
Gp[0].emplace_back(1);
for(int j=0,i=2;i<=n;++i){
while(j&&s[j+1]!=s[i]) j=prenxt[j];
j+=(s[j+1]==s[i]);
prenxt[i]=j;
Gp[j].emplace_back(i);
}
sufnxt[n]=n+1;
Gs[n+1].emplace_back(n);
for(int j=n+1,i=n-1;i>=1;--i){
while(j!=n+1&&s[j-1]!=s[i]) j=sufnxt[j];
j-=s[j-1]==s[i];
sufnxt[i]=j;
Gs[j].emplace_back(i);
}
int tim_pre=0,tim_suf=0;
functiondfs_pre=[&](int x){
inp[x]=++tim_pre;
for(auto t:Gp[x]) dfs_pre(t);
outp[x]=tim_pre;
};
functiondfs_suf=[&](int x){
val[inp[x-1]]=ins[x]=++tim_suf;
for(auto t:Gs[x]) dfs_suf(t);
outs[x]=tim_suf;
};
dfs_pre(0);
dfs_suf(n+1);
for(int i=1;i<=n+1;++i) insert(rt[i],rt[i-1],1,n+1,val[i]);
while(Q--){
int x=read(),y=read();
y=n-y+1;
print(query(rt[outp[x]],rt[inp[x]-1],1,1+n,ins[y],outs[y]));
}
}
return 0;
}
计树
设 \(g_x\) 表示 \(x\) 子树让一个 \(1\sim siz_x\) 的排列在 \(x\) 子树里面放，满足父亲标号小于儿子的方案树
再设 \(dp_{x,id,rk}\) 表示 \(x\) 子树里面点 \(id\) 分配的标号排位是 \(rk\) 的方案数，转移是子树归并，枚举已经合并的子树里面的点 \(x\) 原来的位次和新的位次，小于它和大于它的数任意排列，乘两个组合数以及当前添加儿子 \(t\) 的 \(g_t\)，对于 \(t\) 子树里面的点也是一样
将 \(id\) 这维度固定那么 \((x,rk)\) 的转移过程和树形背包一样，复杂度是 \(\Theta(n^3)\)
使用这两者来求答案，在 \(u,v\) 两个点的 \(\rm LCA\) 处来强制它们相邻，设两个方向 \(\rm LCA\) 的儿子为 \(s_u,s_v\)，枚举 \(u\) 在 \(s_u\) 子树里面的排名和 \(v\) 在 \(s_v\) 子树中的排名，除了 \(dp_{s_u,u,*},dp_{s_v,v,*}\) 值之外还要让两棵树合并，此时将归并进来的子树 \(v\) 的大小视为 \(siz_v-1\) 得到组合数即可
实现的时候枚举已归并子树中的点，由于系数和在新归并儿子 \(t\) 的子树中的排名有关，那么对于每个排名统计 \(t\) 子树中所有点的权值，统一计算，复杂度也是 \(\Theta(n^3)\)。在 \(\rm LCA\) 根链上合并带来的系数在回溯过程中处理
Code Display
const int N=210;
int n,rt,siz[N];
int g[N],ans[N],dp[N][N][N],tmp[N];
int C[N][N];
vector G[N],sub[N];
signed main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=200; C[0][0]=1;
for(int i=1;i<=n;++i){
C[i][0]=1;
for(int j=1;j<=i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
n=read(); rt=read();
for(int i=1;idfs=[&](int x,int fat){
siz[x]=g[x]=1;
for(auto t:G[x]) if(t!=fat) dfs(t,x);
for(auto t:G[x]) if(t!=fat){
int sum=g[x]*dp[t][t][1]%mod*C[siz[x]+siz[t]-2][siz[t]-1]%mod*abs(x-t);
for(auto u:sub[x]){
for(int i=1;i<=siz[t];++i){
int coef=0;
for(auto v:sub[t]) coef+=abs(u-v)*dp[t][v][i];
coef%=mod;
if(!coef) continue;
int val=0;
for(int j=1;j<=siz[x];++j) if(dp[x][u][j]){
val+=dp[x][u][j]*C[i-1+j-2][i-1]%mod*C[siz[x]-j+siz[t]-i][siz[x]-j]%mod;
}
sum+=val%mod*coef%mod*2;
}
}
for(auto u:sub[x]){
rep(i,2,siz[x]) if(dp[x][u][i]){
rep(j,0,siz[t]){
tmp[i+j]+=dp[x][u][i]*C[i-2+j][j]%mod*C[siz[x]+siz[t]-i-j][siz[x]-i]%mod;
}
}
rep(i,1,siz[x]+siz[t]) dp[x][u][i]=mul(g[t],tmp[i]%mod),tmp[i]=0;
}
for(auto u:sub[t]){
rep(i,1,siz[t]) if(dp[t][u][i]){
rep(j,1,siz[x]) tmp[i+j]+=dp[t][u][i]*C[i-2+j][i-1]%mod*C[siz[x]+siz[t]-i-j][siz[x]-j]%mod;
}
rep(i,1,siz[x]+siz[t]) dp[x][u][i]=mul(g[x],tmp[i]%mod),tmp[i]=0;
sub[x].emplace_back(u);
}
siz[x]+=siz[t];
ans[x]=(ans[x]*g[t]%mod*C[siz[x]-2][siz[t]]+ans[t]*g[x]%mod*C[siz[x]-2][siz[t]-1]+sum)%mod;
ckmul(g[x],mul(g[t],C[siz[x]-1][siz[t]]));
}
dp[x][x][1]=g[x];
sub[x].emplace_back(x);
};
dfs(rt,0);
print(ans[rt]);
return 0;
}
数论
将 \(F\) 函数中的 \(a_1\dots a_m\) 变为枚举 \(i\in[1,t],j\in [1,m],e_{i,j}\) ，满足 \(\displaystyle\sum_{j=1}^m e_{i,j}=k_i\)，这也等价于 \(\displaystyle\sum_{i,j} e_{i,j}=n\)
所以答案表达式变成了
\[\sum_{\sum\limits_{i,j}e_{i,j}=n} \prod_{i=1}^t\prod_{j=1}^m [e_{i,j}=0]\times1+[e_{i,j}>0]\times (p_i-1)p^{e_{i,j}-1} \]设 \(H_{i}(x)=1+\sum_{n\ge 1}(p_i-1)p_i^{n-1}x^n\) ，此时答案变成了 \([x^n]\displaystyle \prod_{i=1}^mH_{i}^t(x)\)
拆开 \(H_i(x)\) 中的括号得到 \(H_i(x)=\sum_{n\ge 0}p^{n}x^n-\sum_{n\ge 1}p_i^{n-1}x^n=\dfrac{1-x}{1-p_ix}\) ，通过分治乘法可以得到答案 \(\rm OGF\) 的分子分母
剩下的问题是求 \([x^n]\dfrac{f(x)}{g(x)}\) ，使用 波斯坦-茉莉 算法解决即可
Code Display
const int N=3e6+10;
int r[N],W[N],inv[N];
inline void NTT(vector &f,int lim,int opt){
f.resize(lim);
for(int i=0;i>1]>>1|((i&1)?(lim>>1):0);
if(i>1; W[0]=1; W[1]=ksm(3,(mod-1)/p);
if(opt==-1) W[1]=ksm(W[1],mod-2);
for(int j=2;j G0=Inv(a,(len+1)>>1);
int lim=1; while(lim<=(len<<1)) lim<<=1;
vector tmp,G;
rep(i,0,len-1) tmp.emplace_back(a[i]);
NTT(tmp,lim,1); NTT(G0,lim,1);
for(int i=0;i ret(m+1);
for(int i=0,pw=1;i<=m;++i,ckmul(pw,p[l])){
ret[i]=mul(binom(m,i),pw);
if(i&1) ret[i]=del(0,ret[i]);
}
return ret;
}
int mid=(l+r)>>1;
return Mul(div_con(l,mid),div_con(mid+1,r));
}
inline int Recurrence(vector f,vector g,int n){
while(n){
if(n tmp=g;
for(int i=1;i>=1;
}
if(f.size()) return mul(f[0],ksm(g[0],mod-2));
else return 0;
}
signed main(){
freopen("math.in","r",stdin); freopen("math.out","w",stdout);
n=5e5; fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
ifac[n]=ksm(fac[n],mod-2);
for(int i=n;i>=1;--i) ifac[i-1]=mul(ifac[i],i);
n=read(); t=read(),m=read();
for(int i=1;i<=t;++i) p[i]=read();
vector zi(m*t+1);
for(int i=0;i<=m*t;++i){
zi[i]=binom(m*t,i);
if(i&1) zi[i]=del(0,zi[i]);
}
vector mu=div_con(1,t);
print((Recurrence(zi,mu,n)));
return 0;
}