题解：AT_agc068_d [AGC068D] Sum of Hash of Lexmin

· · 题解

题意：

给定一棵父亲编号小于儿子编号的树，可以交换排列中相邻且呈祖孙关系的两个点。称无法变成字典序更小的排列为合法排列，求所有合法排列的 \sum_i B^{i-1}x_i 之和，n\le100。

思路：

合法等价于不存在“后代紧挨在祖先前面”。 :::info[证明] 若能变小，设首个变化位置由 x_i 变成原来位于 j>i 的 v<x_i，则 x_i,\ldots,x_{j-1} 都与 v 交换过，故均与其呈祖孙关系。从 x_i 开始找到第一个不是 v 严格后代的点，它与前一个点即构成坏相邻关系。 ::: 容斥钦定若干坏相邻关系，形成由后代到祖先的连续链，每次接链乘 -1。枚举贡献点 p，将其所在链作为特殊链，其余链分为左右两个有序序列。设 f_{u,l,r,t} 为子树内左右普通链数为 l,r，是否选了 p 为 t 的带权方案和；权值包含容斥符号、每个位于 p 前面的点贡献的 B，以及选中 p 时贡献的编号 p。未选 p 时，仅左侧点贡献 B；特殊链不计入 l,r。

初始化 f_{u,0,0,0}=1。合并儿子 v，交错排列左右链：

g_{l+a,r+b,t+k}\mathrel{+}= f_{u,l,r,t}f_{v,a,b,k} \binom{l+a}{l}\binom{r+b}{r},\quad t+k\le1.

合并完儿子后加入 u，记当前值为 F，清空 g。接到左右链尾或新建链：

g_{l,r,t}\gets g_{l,r,t}-(lB+r)F\\ g_{l+1,r,t}\gets g_{l+1,r,t}+(l+1)BF\\ g_{l,r+1,t}\gets g_{l,r+1,t}+(r+1)F

若 t=1，还可接到特殊链尾：g_{l,r,1}\mathrel{-}=F。若 t=0，可选 p=u，自成特殊链或接到最后一条左链：

g_{l,r,1}\gets g_{l,r,1}+uF\\ g_{l-1,r,1}\gets g_{l-1,r,1}-uF\quad(l>0)

答案为 \sum_{l,r}f_{1,l,r,1}。时间复杂度 O(n^4)，空间复杂度 O(n^3)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=110,mod=998244353;
int n,B,ans,sz[N],c[N][N];
int f[N][N][N][2],g[N][N][2];
vector<int> edge[N];
void add(int &x,int y){x=(x+y)%mod;}
void sub(int &x,int y){x=(x-y+mod)%mod;}
void clear(int s)
{
    for(int l=0;l<=s;l++)
        for(int r=0;l+r<=s;r++)
            g[l][r][0]=g[l][r][1]=0;
}
void dfs(int u)
{
    f[u][0][0][0]=1;
    for(int v:edge[u])
    {
        dfs(v);
        clear(sz[u]+sz[v]);
        for(int l=0;l<=sz[u];l++)
            for(int r=0;l+r<=sz[u];r++)
                for(int t=0;t<=1;t++)
                {
                    int x=f[u][l][r][t];
                    if(!x) continue;
                    for(int a=0;a<=sz[v];a++)
                        for(int b=0;a+b<=sz[v];b++)
                            for(int k=0;t+k<=1;k++)
                            {
                                int y=f[v][a][b][k];
                                if(!y) continue;
                                add(g[l+a][r+b][t+k],x*y%mod*c[l+a][l]%mod*c[r+b][r]);
                            }
                }
        sz[u]+=sz[v];
        for(int l=0;l<=sz[u];l++)
            for(int r=0;l+r<=sz[u];r++)
                for(int t=0;t<=1;t++)
                    f[u][l][r][t]=g[l][r][t];
    }
    clear(sz[u]+1);
    for(int l=0;l<=sz[u];l++)
        for(int r=0;l+r<=sz[u];r++)
            for(int t=0;t<=1;t++)
            {
                int x=f[u][l][r][t];
                if(!x) continue;
                sub(g[l][r][t],x*l%mod*B);
                sub(g[l][r][t],x*r);
                add(g[l+1][r][t],x*(l+1)%mod*B);
                add(g[l][r+1][t],x*(r+1));
                if(t) sub(g[l][r][1],x);
                else
                {
                    add(g[l][r][1],x*u);
                    if(l) sub(g[l-1][r][1],x*u);
                }
            }
    sz[u]++;
    for(int l=0;l<=sz[u];l++)
        for(int r=0;l+r<=sz[u];r++)
            for(int t=0;t<=1;t++)
                f[u][l][r][t]=g[l][r][t];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>B;
    B%=mod;
    for(int i=2,p;i<=n;i++)
        cin>>p,edge[p].push_back(i);
    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]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    dfs(1);
    for(int l=0;l<n;l++)
        for(int r=0;l+r<n;r++)
            add(ans,f[1][l][r][1]);
    cout<<ans;
    return 0;
}