题解：P11802 【MX-X9-T6】『GROI-R3』Graph

Rain_chr · 2025-02-27 09:49:08 · 题解

Part 1 前言

非常考验基本功的一道题，我想到做法用了两个小时，写+优化又用了两个小时，特写题解以记录。

Part 2 解法

首先预处理出 A_i,B_i,C 分别表示原图中长度为 i 的环数，长度为 i 的链数以及孤立点个数。

首先来推一推 c 次方的性质：

引理 1：一个环长为 x 的环 c 次方之后会分裂成 (x,c) 个环长为 \frac c {(x,c)} 的环

证明显然，不再赘述。

所以只有在新图 G' 中环长相等的环才可能拼在一起，不同环长之间互相独立。

再来推一下对于一个二元组 (a_i,b_i) 表示有 a_i 个环长为 b_i 的环，什么情况下才有 c 次方根。

引理 2：拼成新环的方式一定是将 a_i 个环分成 \frac {a_i} k 组，每组里有 k 个长度为 b_i 的环。

证明：

假设有两种拼出环的方式，分别用 p 个长为 b_i 的环和用 q 个长为 b_i 的环拼成一个新环，那么根据引理 1 有：

也就是

于是我们可以得到：

我们惊奇的发现，对于两种合法的方案，他们的 gcd 同样合法，所以我们就证明了最终方案中，我们只会不断的拼成一种长度的环。

更进一步，可以得到引理 2 的一个推论：

设 k_{min} 是最小的合法的 k，任意合法的 k' 均满足 k_{min}|k'

所以我们可以得到判定的最简形式：

暴力求出 k_{min}，判断是否 [k_{min}|a_i]

现在可以着手来审视 DP 了，我们根据判定形式，枚举环长依次讨论。这个地方我还卡了一下，我一直在想从大往小枚举环长是怎么记录链是否使用了，后来突然想到只需要从小往大枚举环长然后依次加入未使用的连就可以了，于是我们可以设 f_{i,j,k} 表示当前环长为 i，有 j 条长度为 i 的链，剩下 k 个孤立点。转移分两步：

1. f_{i,j+B_i,k-j} \leftarrow f_{i-1,j,k}\times A_k^j

这是因为当枚举的环长增加时，相应的要在链的末尾添加一个孤立点，选取孤立点对应到每条链的方案是 A_k^j。注意这里不应该乘 2^j，因为环的缘故我们钦定每次只会加在末尾，不然会算重。

2. f_{i,j_1,k_1} \leftarrow \frac{f_{i,j_1-j_2,k_1-k_2i}C_{k_2}^{k_1}A_{k_1}^{k_2i}}{i^{k_2}k_2!} [k_{min}|j_1+k_1+A_i]

式子非常丑陋，考虑枚举闭口的链条数 j_2 以及使用孤立点拼成的环数 k_2，自己稍微推一推式子也能得到一样的结果。

然后这样子通过一堆分析可以分析到 O(n^4)，详见其他题解，我感性理解这样跑得很快，事实上的确如此，考虑怎么优化到 O(n^3)。

我们可以发现除了最后的转移条件，转移式的其余部分是两维互相独立的，无论是下标还是系数都是如此。

于是考虑分步转移，最后的转移条件可以视作只在 \bmod k_{min} 的同余类中进行两步转移，具体实现可以看代码。

Part 3 总结

这是一道非常考验 DP 基本功的题目，题目未必困难，但是推导过程一环套一环，适合锻炼系统性做题思维。

Part 4 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
int A[N],B[N],C;//分别表示环的个数,链的个数,以及孤立点的个数
int in[N];
bool use[N];
int n,c;
int f[N][N];//设f[i][j][k]表示目前考虑长度为i的环,有j条长为i的链,孤立点数量为k
int tmp1[N][N],tmp2[N][N];
const int mod=998244353;
void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int jc[N],inv[N],Inv[N];
int F(int x,int y)
{
    if(x<0||y<0||x<y) return 0;
    return 1ll*jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int G(int x,int y)
{
    if(x<0||y<0||x<y) return 0;
    return 1ll*jc[x]*inv[x-y]%mod;
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>c;
    jc[0]=jc[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++) jc[i]=1ll*jc[i-1]*i%mod;
    for(int i=2;i<=n;i++) inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
    memcpy(Inv,inv,sizeof(Inv));
    for(int i=2;i<=n;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]!=-1) in[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]||use[i]) continue;
        if(a[i]==-1) C++;
        else
        {
            int p=i,cnt=0;
            while(p!=-1) in[p]=0,use[p]=1,p=a[p],cnt++;
            B[cnt]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) continue;
        int p=i,cnt=0;
        do{cnt++,in[p]=0,p=a[p];}while(p!=i);
        A[cnt]++;
    }
    f[0][C]=1;
    int sumb=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=sumb;j++) for(int k=0;k<=C;k++) tmp2[j][k]=0;
        for(int j=0;j<=sumb;j++)
            for(int k=j;k<=C;k++)
                add(tmp2[j+B[i]][k-j],1ll*f[j][k]*G(k,j)%mod);
        for(int j=0;j<=sumb;j++) for(int k=0;k<=C;k++) f[j][k]=0;
        sumb+=B[i];
        int x=0;
        while(++x) if(__gcd(i,c/__gcd(c,x))==1) break;
        for(int t=0;t<x;t++)
        {
            for(int j=0;j<=min(sumb,n/i);j++) for(int k=0;k<=C;k++) tmp1[j][k]=0;
            for(int j2=(t-A[i]%x+x)%x;j2<=min(sumb,n/i);j2+=x)
                for(int j1=j2;j1<=min(sumb,n/i);j1++)
                    for(int k1=0;k1<=C;k1++)
                        if(tmp2[j1][k1])
                            add(tmp1[j1-j2][k1],1ll*tmp2[j1][k1]*F(j1,j2)%mod);
            int now=1;
            for(int k2=0;i*k2<=C;k2++,now=1ll*now*Inv[i]%mod)
                if((n*x-k2)%x==t)
                    for(int j1=0;j1<=min(sumb,n/i);j1++)
                        for(int k1=i*k2;k1<=C;k1++)
                            if(tmp1[j1][k1])
                                add(f[j1][k1-k2*i],1ll*tmp1[j1][k1]*now%mod*G(k1,k2*i)%mod*inv[k2]%mod);
        }
    }
    cout<<f[0][0]<<'\n';
    return 0;   
}