【学习笔记】[AGC063E] Child to Parent-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学习笔记】[AGC063E] Child to Parent。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

提供一个多项式做法。

分别设 $f_{u,i},g_{u,i}$ 表示以 $u$ 为根时， $a_u=i$ 和 $a_u\ge i$ 的方案数，合并子树 $v$ 时，转移如下：

$f_{u,i}=\sum f_{u,i-kr}\times g_{v.k}$

初值为 $f_{u,a_u}=1$ 。

注意到 DP 的值域很大，通常情况下我们可以考虑用拉格朗日插值法来处理，但是实际上只要满足信息封闭也是可以转移的。我们不妨将其转化成多项式的形式，从而来观察需要记录哪些信息。

设：
$F_u(x)=\sum f_{u,i}x^i\\G_u(x)=\sum g_{u,i}x^i$

转移大致分为以下几步：

$F_u(x)\gets \prod G_v(x)\\F_u(x)\gets x^{a_i}F_u(x^r)\\ G_u(x)\gets F_u(x)+\frac{F_u(1)-F_u(x)}{1-x}$

其中最后一个式子是在求后缀和，之所以不能写成 $\frac{1}{1-x^{-1}}$ 的原因是生成函数不能有次数 $< 0$ 的项。

现在问题在于，要求出 $F_u(1)$ 就必须维护各项系数，显然次数太高就寄了。考虑一步非常巧妙的转化：我们设 $G'_u(x)=G_u(x+1),F'_u(x)=F_u(x+1)$ ，则 $F'_u(0)=F_u(1)$ ，而 $F'_u(0)$ 其实就是常数项，又因为要求的答案也是常数项，这样我们只用算次数较低的项，信息就封闭了。

新的转移大致为：

$F'_u(x)\gets \prod G'_v(x)\\$

这是因为

$F'_u(x)=F_u(x+1)=\prod G_v(x+1)=\prod G'_v(x)$

$F_u'(x)\gets (x+1)^{a_i}F_u'((x+1)^r-1)$

这是因为

$F'_u(x)=F_u(x+1)=(x+1)^{a_i}F_u((x+1)^r)=(x+1)^{a_i}F_u'((x+1)^r-1)$

$G'_u(x)=F'_u(x)+\frac{F'_u(0)-F'_u(x)}{-x}$

如果我们只保留前 $k$ 项，那么因为要除以 $x$ ，所以每次转移完后最后一项都会损失掉。但是因为答案是第一项的值，所以我们对于每个节点保留 $dep_u$ 项即可。

复杂度 $O(n^3)$ 。

~~麻了，好像和官方题解长得一样。~~文章来源地址https://www.toymoban.com/news/detail-807686.html

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int mod=998244353;
int n,fa[305],dep[305];
ll r,fac[305],inv[305],ifac[305],to[305][305],f[305][305],g[305][305],a[305],res;
vector<int>G[305];
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
ll binom(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(int n){
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
    ifac[1]=1;for(int i=2;i<=n;i++)ifac[i]=mod-ifac[mod%i]*(mod/i)%mod;
}
void dfs(int u){
    f[u][0]=1;
    for(auto v:G[u]){
        dep[v]=dep[u]+1,dfs(v);
        memset(f[0],0,sizeof f[0]);
        for(int i=0;i<=dep[v];i++)for(int j=0;i+j<=dep[v];j++)(f[0][i+j]+=f[u][i]*g[v][j])%=mod;
        memcpy(f[u],f[0],sizeof f[0]);
    }
    memset(f[0],0,sizeof f[0]);
    for(int i=0;i<=dep[u]+1;i++)for(int j=0;j<=dep[u]+1;j++)(f[0][j]+=f[u][i]*to[i][j])%=mod;
    memset(f[u],0,sizeof f[u]);
    ll mul=1;
    for(int i=0;i<=dep[u]+1;i++){
        for(int j=0;i+j<=dep[u]+1;j++)(f[u][i+j]+=mul*f[0][j])%=mod;
        mul=mul*(a[u]-i)%mod*ifac[i+1]%mod;
    }
    for(int i=0;i<=dep[u];i++)g[u][i]=(f[u][i]+f[u][i+1])%mod;
}
signed main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;for(int i=2;i<=n;i++)cin>>fa[i],G[fa[i]].pb(i);
    cin>>r;init(n);
    to[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            ll mul=1;int sgn=(i-j&1)?-1:1;
            for(int k=0;k<=n;k++){
                (to[i][k]+=sgn*binom(i,j)*mul)%=mod;
                mul=mul*((j*r-k)%mod)%mod*ifac[k+1]%mod;
            }
        }
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1);
    cout<<(f[1][0]+mod)%mod;
}