UOJ#50. 【UR #3】链式反应

枚举两个子树，由于带标号，直接枚举大小再除以个2就行了。

三个多项式卷在一起就离谱，先把两个多项式卷在一起的结果\(g_i=\sum\limits_{x=1}^{i-1}f_xf_{i-x}\)求出来，再把它和另外那个固定的多项式卷起来就是最终的答案。

这个\(g\)他不是一个普通的半在线卷积，他是两个\(f\)卷在一起的结果，有可能考虑\([l,mid]\)给\([mid+1,r]\)的贡献的时候，\(r-l>mid\)，这个时候你并不知道\(f\)的值。其实这个东西可以改变一下。这个转移是对称的，可以只考虑\(i<j\)的时候\(2f_if_j\)对\(f_{i+j}\)的贡献。这样的话，cdq分治的过程中变成了考虑两种贡献，一种是\(i\in[l,mid],j\in[1,l-1],i+j\in[mid+1,r],f_{i+j}=f_if_j\)，另一种是\(i\in[l,mid],j\in[l,mid],i+j\in[mid+1,r]\)。第一种贡献需要有\(2\)的常数，第二种卷积的过程中自然有多少就是多少，不用管了。这个想法大概所有cdq分治里有3个东西卷到一起或者自己卷自己的时候都可以用到。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
typedef long long ll;
#define N 2000102
const int p=998244353,iv=499122177;
int n,dp[N],g[N],fac[N],finv[N],inv[N],rev[N],c[N],ta[N],tb[N];
char ch[N];
inline int ksm(int d,int k){int ret=1;while(k){if(k&1)ret=1ll*ret*d%p;d=1ll*d*d%p;k>>=1;}return ret;}
void ntt(int x[],int len,int mde)
{for(int i=0;i<len;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
    for(int i=2;i<=len;i<<=1)
    {int wn=ksm(3,(p-1)/i);if(mde<0)wn=ksm(wn,p-2);
        for(int j=0,stp=i>>1;j<len;j+=i)for(int k=j,w=1;k<j+stp;k++,w=1ll*w*wn%p)
        {int t1=x[k],t2=1ll*x[k+stp]*w%p;x[k]=(t1+t2)%p,x[k+stp]=(t1-t2+p)%p;}
    }if(mde<0)for(int i=0,te=ksm(len,p-2);i<len;i++)x[i]=1ll*x[i]*te%p;
}
void solve(int l,int r)
{
    if(l==r){dp[l]=1ll*dp[l]*iv%p*inv[l]%p;return;}
    int mid=(l+r)>>1,tle=1;solve(l,mid);
    while(tle<=(r-l+1)*2)tle<<=1;
    for(int i=1;i<=tle;i++){rev[i]=rev[i>>1]>>1;if(i&1)rev[i]|=tle>>1;}
    for(int i=0;i<tle;i++)ta[i]=tb[i]=0;
    for(int i=l;i<=mid;i++)ta[i-l]=dp[i];
    for(int i=1;i<=r-l;i++)
    {
        if(i<l)tb[i]=2ll*dp[i]%p;
        else if(i<=mid)tb[i]=dp[i];
    }
    ntt(ta,tle,1);ntt(tb,tle,1);
    for(int i=0;i<tle;i++)ta[i]=1ll*ta[i]*tb[i]%p;
    ntt(ta,tle,-1);
    for(int i=mid+1;i<=r;i++)(g[i]+=ta[i-l])%=p;
    for(int i=0;i<tle;i++)ta[i]=tb[i]=0;
    for(int i=l;i<=mid;i++)ta[i-l]=g[i];
    for(int i=0;i<=r-l;i++)tb[i]=c[i];
    ntt(ta,tle,1);ntt(tb,tle,1);
    for(int i=0;i<tle;i++)ta[i]=1ll*ta[i]*tb[i]%p;
    ntt(ta,tle,-1);
    for(int i=mid+1;i<=r;i++)(dp[i]+=ta[i-l-1])%=p;
    solve(mid+1,r);
}
int main()
{
    fac[0]=finv[0]=fac[1]=finv[1]=inv[1]=1;
    for(int i=2;i<=200000;i++)
    {
        inv[i]=1ll*(p-p/i)*inv[p%i]%p;
        fac[i]=1ll*fac[i-1]*i%p;finv[i]=1ll*finv[i-1]*inv[i]%p;
    }
    scanf("%d%s",&n,ch);
    for(int i=0;i<n;i++)if(ch[i]==‘1‘)c[i]=finv[i];dp[1]=2;
    solve(1,n);
    for(int i=1;i<=n;i++)printf("%d\n",1ll*dp[i]*fac[i]%p);
}```

UOJ#50. 【UR #3】链式反应

原文：https://www.cnblogs.com/LebronDurant/p/14479822.html