7.2 冲刺国赛自测 9
T1 字符串
一个合法位置 \([l,r]\) 代表 \([1,x]\) 与 \([l,l+x-1]\) 相同,\([y,n]\) 与 \([r-y+1,r]\) 相同,类似 \(x\in \mathrm{Border}(l+x-1)\)。
对正反串做 KMP,建失配树,类似要求 \(x\) 子树和 \(y\) 子树的交,而 \((l+x-1)+1=(r-y+1)\) 所以正串失配树子树里节点 \(u\) 对应反串失配树子树里节点 \(n-u\),二维数点即可。
点击查看代码
int rt[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
int ch[maxn*40][2],tot;
int siz[maxn*40];
inline void clear(){
tot=0;
memset(ch,0,sizeof(ch));
memset(siz,0,sizeof(siz));
}
inline void new_node(int &pos){
ch[++tot][0]=ch[pos][0],ch[tot][1]=ch[pos][1],siz[tot]=siz[pos];
pos=tot;
}
void insert(int &pos,int l,int r,int p){
new_node(pos);
++siz[pos];
if(l==r) return;
if(p<=mid) insert(ch[pos][0],l,mid,p);
else insert(ch[pos][1],mid+1,r,p);
}
int query(int lpos,int rpos,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return siz[rpos]-siz[lpos];
int res=0;
if(pl<=mid) res+=query(ch[lpos][0],ch[rpos][0],l,mid,pl,pr);
if(pr>mid) res+=query(ch[lpos][1],ch[rpos][1],mid+1,r,pl,pr);
return res;
}
#undef mid
}S;
int t;
int n,q;
char s1[maxn],s2[maxn];
int nxt1[maxn],nxt2[maxn];
vector<int> E1[maxn],E2[maxn];
int fa1[maxn],siz1[maxn],dfn1[maxn],dfncnt1;
int fa2[maxn],siz2[maxn],dfn2[maxn],dfncnt2;
int id[maxn];
inline void get_nxt(){
nxt1[1]=0;
E1[0].push_back(1);
for(int i=2,j=0;i<=n;++i){
while(j&&s1[i]!=s1[j+1]) j=nxt1[j];
if(s1[i]==s1[j+1]) ++j;
nxt1[i]=j;
E1[j].push_back(i);
}
nxt2[1]=0;
E2[0].push_back(1);
for(int i=2,j=0;i<=n;++i){
while(j&&s2[i]!=s2[j+1]) j=nxt2[j];
if(s2[i]==s2[j+1]) ++j;
nxt2[i]=j;
E2[j].push_back(i);
}
}
void dfs1(int u,int f){
fa1[u]=f,siz1[u]=1;
if(u) dfn1[u]=++dfncnt1,id[dfn1[u]]=u;
for(int v:E1[u]){
if(v==f) continue;
dfs1(v,u);
siz1[u]+=siz1[v];
}
}
void dfs2(int u,int f){
fa2[u]=f,siz2[u]=1;
if(u) dfn2[u]=++dfncnt2;
for(int v:E2[u]){
if(v==f) continue;
dfs2(v,u);
siz2[u]+=siz2[v];
}
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
t=read();
while(t--){
n=read(),q=read();
for(int i=0;i<=n;++i){
nxt1[i]=nxt2[i]=0;
E1[i].clear(),E2[i].clear();
dfncnt1=dfncnt2=0;
fa1[i]=siz1[i]=dfn1[i]=fa2[i]=siz2[i]=dfn2[i]=0;
}
S.clear();
scanf("%s",s1+1);
for(int i=1;i<=n;++i) s2[i]=s1[n-i+1];
get_nxt();
dfs1(0,0);
dfs2(0,0);
rt[0]=0;
for(int i=1;i<=n;++i){
int j=dfn2[n-id[i]];
rt[i]=rt[i-1];
if(j) S.insert(rt[i],1,n,j);
}
while(q--){
int x=read(),y=read();
printf("%d\n",S.query(rt[dfn1[x]-1],rt[dfn1[x]+siz1[x]-1],1,n,dfn2[y],dfn2[y]+siz2[y]-1));
}
}
return 0;
}
T2 计树
魔幻转化是枚举 \(x\in [1,n)\),令 \(p_i=[p_i>x]\),求所有 \(p\) 中相邻位置不同的个数和就是答案,正确性在于 \(p_i=a,p_{i+1}=b\ (a<b)\) 时,\(p_i\neq p_{i+1}\) 恰好为 \(x\in [a,b)\),贡献就是 \(b-a\)。
考虑 DP,目标是子树内构成 \(p\) 的子序列中某两个相邻不同的方案数,同时需要维护出每个位置上 \(0/1\) 的方案数,也需要维护出子树内方案总数。
设 \(f_u\) 为 \(u\) 子树内合法 \(p\) 序列方案数,\(g_{u,k,0/1}\) 为 \(u\) 子树内 \(p_k=0/1\) 的方案数,\(h_{u,k}\) 为 \(u\) 子树内 \(p_k\neq p_{k+1}\) 的方案数。
\(f\) 转移不断乘 \(f_v\) 和组合数即可。
\(g\) 转移讨论 \(k\) 来自已经合并过的子树或是 \(v\),其余位置的排布方案乘组合数。
\(h\) 讨论同理,更复杂一点需要讨论 \(k\) 与 \(k+1\) 分别来自哪里,方案依旧是组合数。
转移精细实现复杂度是树上背包 \(O(n^2)\)。
根据题意,\(p\) 序列第一个元素一定是 \(u\),所以 \(p_1\) 实际根据 \(x\) 固定,最后把 \(u\) 加进去时先向右平移,再算 \(1\) 处值即可。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int n,rt;
vector<int> E[maxn];
int fact[maxn],inv_fact[maxn];
inline int C(int N,int M){
if(N<M) return 0;
return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}
int siz[maxn];
int f[maxn],g[maxn][maxn][2],h[maxn][maxn],tmpg[maxn][2],tmph[maxn];
void dfs(int u,int fa,int x){
f[u]=1;
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u,x);
for(int i=1;i<=siz[u]+siz[v];++i) tmpg[i][0]=tmpg[i][1]=0,tmph[i]=0;
for(int i=0;i<=siz[u];++i){
for(int j=0;j<=siz[v];++j){
if(i){
tmpg[i+j][0]=(tmpg[i+j][0]+1ll*g[u][i][0]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
tmpg[i+j][1]=(tmpg[i+j][1]+1ll*g[u][i][1]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
}
if(j){
tmpg[i+j][0]=(tmpg[i+j][0]+1ll*f[u]*g[v][j][0]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
tmpg[i+j][1]=(tmpg[i+j][1]+1ll*f[u]*g[v][j][1]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
}
}
}
for(int i=0;i<=siz[u];++i){
for(int j=0;j<=siz[v];++j){
if(i&&i<siz[u]){
tmph[i+j]=(tmph[i+j]+1ll*h[u][i]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
}
if(j&&j<siz[v]){
tmph[i+j]=(tmph[i+j]+1ll*f[u]*h[v][j]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
}
if(i&&j<siz[v]){
tmph[i+j]=(tmph[i+j]+1ll*g[u][i][0]*g[v][j+1][1]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
tmph[i+j]=(tmph[i+j]+1ll*g[u][i][1]*g[v][j+1][0]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
}
if(i<siz[u]&&j){
tmph[i+j]=(tmph[i+j]+1ll*g[u][i+1][0]*g[v][j][1]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
tmph[i+j]=(tmph[i+j]+1ll*g[u][i+1][1]*g[v][j][0]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
}
}
}
f[u]=1ll*f[u]*f[v]%mod*C(siz[u]+siz[v],siz[v])%mod;
siz[u]+=siz[v];
for(int i=1;i<=siz[u];++i) g[u][i][0]=tmpg[i][0],g[u][i][1]=tmpg[i][1],h[u][i]=tmph[i];
}
++siz[u];
for(int i=siz[u];i>1;--i) g[u][i][0]=g[u][i-1][0],g[u][i][1]=g[u][i-1][1],h[u][i]=h[u][i-1];
int now=(u>x);
g[u][1][0]=g[u][1][1]=h[u][1]=0;
g[u][1][now]=f[u];
h[u][1]=g[u][2][now^1];
}
int ans;
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read(),rt=read();
fact[0]=1;
for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
inv_fact[0]=1,inv_fact[n]=q_pow(fact[n],mod-2,mod);
for(int i=n-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
for(int x=1;x<n;++x){
memset(siz,0,sizeof(siz));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(h,0,sizeof(h));
dfs(rt,0,x);
for(int i=1;i<n;++i) ans=(ans+h[rt][i])%mod;
}
printf("%d\n",ans);
return 0;
}
T3 数论
不妨把每个 \(p_i\) 和 \(a_j\) 全部拆开,改为 \(p_i\) 在 \(a_j\) 的次数是 \(c_{i,j}\) 且 \(\sum_{i,j} c_{i,j}=N\)。
答案就可以写成:
\[\sum_{\sum_{i,j} c_{i,j}=N}\prod_{i=1}^n\prod_{j=1}^m [c_{i,j}=0]+[c_{i,j}>0](p_i-1)p_i^{c_{i,j}-1} \]\(\sum_{i,j} c_{i,j}=N\) 容易想到生成函数,那么 \(F_i(x)\) 对应质数 \(p_i\),则:
\[F_i(x)=1+\sum_{k\ge 1} (p_i-1)p_i^{c_{i,j}-1} \]求封闭形式,得到:
\[F_i(x)=\dfrac{1-x}{1-p_ix} \]最终要求:
\[[x^N]\prod_{i=1}^n F_i(x)^m=[x^N]\left(\dfrac{\prod_{i=1}^n (1-x)}{\prod_{i=1}^n (1-p_ix)}\right)^m \]可以分治乘+快速幂,最后得到一个形如 \([x^N]\dfrac{f(x)}{g(x)}\) 的结果,Bostan-Mori 算法解决,复杂度 \(O(n\log n\log N)\)。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int rev[maxn];
int base,w[maxn];
struct Poly{
const static int g=3;
const static int inv_g=332748118;
int deg;
vector<ull> f;
ull& operator[](const int &i){return f[i];}
ull operator[](const int &i)const{return f[i];}
inline void set(int L){deg=L;f.resize(L);}
inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
inline void NTT(int L,bool type){
set(L);
for(int i=1;i<L;++i){
rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
if(i<rev[i]) swap(f[i],f[rev[i]]);
}
for(int d=1;d<L;d<<=1){
base=q_pow(type?g:inv_g,(mod-1)/(2*d),mod);
w[0]=1;
for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
for(int i=0;i<L;i+=d<<1){
for(int j=0;j<d;++j){
ull x=f[i+j],y=f[i+d+j]*w[j]%mod;
f[i+j]=x+y,f[i+d+j]=x-y+mod;
}
}
}
for(int i=0;i<L;++i) f[i]%=mod;
if(!type){
int inv_L=q_pow(L,mod-2,mod);
for(int i=0;i<L;++i) f[i]=f[i]*inv_L%mod;
}
}
inline Poly Pow(int k){
Poly res=(*this),base=(*this);
--k;
int L=deg;
while(k){
L<<=1;
base.NTT(L,1);
if(k&1){
res.NTT(L,1);
for(int i=0;i<L;++i) res[i]=res[i]*base[i]%mod;
res.NTT(L,0);
}
for(int i=0;i<L;++i) base[i]=base[i]*base[i]%mod;
base.NTT(L,0);
k>>=1;
}
return res;
}
};
int a[maxn];
Poly Conquer(int l,int r){
if(l==r){
Poly F;
F.set(2);
F[0]=1ull,F[1]=(ull)mod-a[l];
return F;
}
int mid=(l+r)>>1;
Poly F=Conquer(l,mid),G=Conquer(mid+1,r);
int L=1;
while(L<=(r-l+1)) L<<=1;
Poly H;
H.set(L);
F.NTT(L,1),G.NTT(L,1);
for(int i=0;i<L;++i) H[i]=F[i]*G[i]%mod;
H.NTT(L,0);
return H;
}
inline void Bostan_Mori(int N,Poly F,Poly G){
int L=F.deg;
Poly H,A,B;
F.set(L<<1),G.set(L<<1),H.set(L<<1),A.set(L<<1),B.set(L<<1);
while(N){
H=G;
for(int i=1;i<L;i+=2) H[i]=mod-H[i];
F.NTT(L<<1,1),G.NTT(L<<1,1),H.NTT(L<<1,1);
for(int i=0;i<L<<1;++i) A[i]=F[i]*H[i]%mod,B[i]=G[i]*H[i]%mod;
A.NTT(L<<1,0),B.NTT(L<<1,0);
for(int i=0;i<L;++i) B[i]=B[i*2];
for(int i=0;i<L;++i) A[i]=A[2*i+(N&1)];
A.clear(L,(L<<1)-1),B.clear(L,(L<<1)-1);
F=A,G=B;
N>>=1;
}
printf("%llu\n",F[0]*q_pow((int)G[0],mod-2,mod)%mod);
}
int N,n,m;
int p[maxn];
int main(){
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
N=read(),n=read(),m=read();
for(int i=1;i<=n;++i) p[i]=read();
Poly F,G;
for(int i=1;i<=n;++i) a[i]=1;
F=Conquer(1,n);
F=F.Pow(m);
for(int i=1;i<=n;++i) a[i]=p[i];
G=Conquer(1,n);
G=G.Pow(m);
Bostan_Mori(N,F,G);
return 0;
}