AGC065F 题解

· · 题解

Problem Link

考虑如何判定图合法，在圆方树上判定原图的每个点双，计算每个点是否要在该点双内匹配，如果同时有要匹配和不要匹配的点，那么必定能找到这样的两个相邻的点，把这个要匹配的点其他出边都删掉后求生成树，则必然无解。

所以每个点双内的点要么都要匹配，要么都不用匹配，都不用匹配的情况是平凡的，只要考虑每个点都要匹配的情况。

手玩发现如果图中能分解出 s\to t 的三条路径，则可以通过调整每条链长的奇偶性构造无解，所以这种情况下只有偶环作为点双才合法（一条边看成大小为 2 的偶环）。

那么我们首先要算出 n 个点的点双联通图个数，设 f_{n,m} 表示 n 个点有 m 个点双连通分量的图数，不妨用 m>2 的 f_{n,m} 容斥计算 f_{n,1}。

则对圆方树形态计数，记每个方点的儿子个数为 a_1\sim a_m，则每个方点内部方案数 \prod f_{a_i+1,1}，然后考虑连成树的代价，把每个方点看成大小为 a_i 的连通块，以及一个大小为 1 的连通块（根），根据 Prufer 定理方案数为 n^{m-1}\prod a_i，但注意实际上一个方点向父亲的连边只有一种起点，而非 a_i 种，因此还要除以 \prod a_i。

组合数处理每个点的标号问题，则 f_{n,m}=n^{m-1}(n-1)!\sum\limits_{\sum a_i=n-1}\prod\dfrac{f_{a_i+1,1}}{a_i!}，维护 f_{n,1} 的背包即可。

然后是原问题，依旧从圆方树的结构入手，每个方点有需要或不需要匹配两种状态，注意到不存在两个相邻的方点都需要匹配，这是显然的。

因此我们把所有偶环对应的方点缩成一个点，然后就变成了普通的圆方树计数，类似上面的方法枚举新树方点个数然后计算即可，同样可以背包处理。

时间复杂度 \mathcal O(n^3)。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,q,r; uLL m;
inline void init(const ull &B) { b=B,m=(uLL(1)<<64)/B; }
inline ull mod(const ull &a) {
    r=a-((m*a)>>64)*b;
    return r>=b?r-b:r;
}
}
#define o(x) FastMod::mod(x)
int n,MOD;
ll C[505][505],f[505][505],g[505],h[505],fac[505],ifac[505],p[505][505],q[505][505];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=o(a*a),b>>=1) if(b&1) s=o(s*a); return s; }
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>MOD,FastMod::init(MOD);
    for(int i=fac[0]=ifac[0]=1;i<=n;++i) ifac[i]=ksm(fac[i]=o(fac[i-1]*i));
    for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=o(C[i-1][j]+C[i-1][j-1]);
    for(int i=1;i<=n;++i) {
        g[i]=h[i]=ksm(2,i*(i-1)/2);
        for(int j=1;j<i;++j) g[i]=o(g[i]+o((MOD-g[j])*h[i-j])*C[i-1][j-1]);
    }
    p[0][0]=1;
    for(int i=2;i<=n;++i) {
        for(int j=2;j<i;++j) for(int k=1;k<=n;++k) {
            p[k][i-1]=o(p[k][i-1]+o(p[k-1][i-j]*f[j][1])*C[i-1][j-1]);
        }
        f[i][1]=g[i];
        for(int j=2;j<i;++j) f[i][j]=o(o(ksm(i,j-1)*p[j][i-1])*ifac[j]),f[i][1]=o(f[i][1]+MOD-f[i][j]);
        p[1][i-1]=f[i][1];
    }
    memset(h,0,sizeof(h)),h[2]=1;
    for(int i=4;i<=n;i+=2) h[i]=o((MOD+1)/2*fac[i-1]);
    for(int i=2;i<=n;i+=2) q[1][i-1]=o(h[i]*i);
    for(int j=2;j<=n/2;++j) for(int s=2;s<=n;++s) for(int i=2;i<=s;i+=2) {
        q[j][s]=o(q[j][s]+o(o(q[j-1][s-i]*h[i])*i)*C[s][i]);
    }
    ll ans=h[n];
    for(int m=2;m<=n/2;++m) for(int k=1;k<m;++k) {
        ans=o(ans+o(o(o(ksm(n,k-1)*p[k][m-1])*ifac[k])*q[m][n-1])*ifac[m-1]);
    }
    cout<<ans<<"\n";
    return 0;
}