数图 / Grafy PA 2019 Final

[PA 2019 Final] 数图 / Grafy

我不会容斥。

求出 nn 个节点的满足以下条件的有标号有向简单图的数量：

  • ∀1≤i≤n\forall 1\le i\le n，degout⁡(i)=degin⁡(i)=2\operatorname{deg_{out}}(i)=\operatorname{deg_{in}}(i)=2。

这里，degout⁡(u)\operatorname{deg_{out}}(u) 指节点 uu 的出度，degin⁡(u)\operatorname{deg_{in}}(u) 指节点 uu 的入度。

你只需要输出答案对给定大素数 pp 取模后的结果。

n≤500n\le 500。

首先，将图转化为一个邻链表存储。即改为计数 b[0⋯2n−1]b[0\cdots 2n-1]，其中 b2ib_{2i} 和 b2i+1b_{2i+1} 表示 ii 的两条邻边。

考虑到顺序问题过于麻烦，考虑忽略顺序，即忽略一个点的出边和入边的顺序。对于 bb 数组相当于改为计数一个 aa 数组，满足 aa 为一个 0∼2n−10\sim2n-1 的排列。并满足 bi=⌊ai2⌋b_i=\lfloor\frac{a_i}{2}\rfloor。

接着，把所有限制写下来：

  • b2i≠b2i+1b_{2i}\ne b_{2i+1}。
  • b2i≠ib_{2i}\ne i。
  • b2i+1≠ib_{2i+1}\ne i。

那么相当于要计数：

∑a∏i[b2i≠b2i+1][b2i≠i][b2i+1≠i]\sum_a\prod_i[b_{2i}\ne b_{2i+1}][b_{2i}\ne i][b_{2i+1}\ne i]

将里面的展开：

[b2i≠b2i+1][b2i≠i][b2i+1≠i]=(1−[b2i≠b2i+1])(1−[b2i≠i])(1−[b2i+1≠i])=1−[b2i≠b2i+1]−[b2i≠i]−[b2i+1≠i]+2[b2i=i][b2i+1=i]\begin{aligned}[b_{2i}\ne b_{2i+1}][b_{2i}\ne i][b_{2i+1}\ne i]&=(1-[b_{2i}\ne b_{2i+1}])(1-[b_{2i}\ne i])(1-[b_{2i+1}\ne i])\\&=1-[b_{2i}\ne b_{2i+1}]-[b_{2i}\ne i]-[b_{2i+1}\ne i]+2[b_{2i}=i][b_{2i+1}=i]\end{aligned}

那么就要计数：

∑a∏i1−[b2i≠b2i+1]−[b2i≠i]−[b2i+1≠i]+2[b2i=i][b2i+1=i]\sum_a\prod_i 1-[b_{2i}\ne b_{2i+1}]-[b_{2i}\ne i]-[b_{2i+1}\ne i]+2[b_{2i}=i][b_{2i+1}=i]

考虑钦定 ii 项个满足 [b2i≠i][b_{2i}\ne i]，jj 个项满足 [b2i+1≠i][b_{2i+1}\ne i]，kk 个项满足 [b2i≠b2i+1][b_{2i}\ne b_{2i+1}]，tt 个项满足 [b2i=i][b2i+1=i][b_{2i}=i][b_{2i+1}=i] 。则有 w=n−i−j−k−tw=n-i-j-k-t 个项任意选择。

那么首先，我们要钦定这些项的位置，有 (ni,j,k,t,w)\binom{n}{i,j,k,t,w} 种方案。

然后，序列 aa 任意排序。但是由于有 i+ji+j 个项中 b2ib_{2i} 和 b2i+1b_{2i+1} 有一个被强制钦定为 ii，k+tk+t 有两个都被强制钦定。于是总共只有 n+w−k−tn+w-k-t 个项任选，即 (n+w−k−t)!(n+w-k-t)! 中方案。

紧接着，我们应该看 i,j,k,t,wi,j,k,t,w 内部对应的方案。

Case #1: i,ji,j

由于 ii 类的项被强制钦定 b2i=ib_{2i}=i，即 a2i=2i/2i+1a_{2i}=2i/2i+1，故每一个项有两种方案。由于 [b2i≠i][b_{2i}\ne i] 的容斥系数为 −1-1，故每一个项会产生 −2-2 的贡献，一共就是 (−2)i(-2)^i 。

jj 同理，为 (−2)j(-2)^j 。

Case #2: tt

tt 类最简单，一共只有 (a2i,a2i+1)=(2i,2i+1)/(2i+1,2i)(a_{2i},a_{2i+1})=(2i,2i+1)/(2i+1,2i) 两种方案，由于容斥系数为 22 ，故有 22t2^{2t} 的贡献。

Case #3: kk

这种最麻烦。由于只钦定了 b2i=b2i+1b_{2i}=b_{2i+1}，因此 b2ib_{2i} 必然没有出现在被 i,j,ti,j,t 类限制的项中，于是只能出现在 k,wk,w 类出现的项，于是有 (k+wk)k!\binom{k+w}{k}k! 中钦定方案。然后类似的，像 tt 类，每一个有 −2-2 的贡献。于是总共有 (k+wk)k!(−2)k\binom{k+w}{k}k!(-2)^k 中方案。

Case #4: pp

∑i+j+k+t+w=n(ni,j,k,t,w)(n+w−k−t)!(−2)i(−2)j(k+wk)k!(−2)k22t\sum_{i+j+k+t+w=n}\binom{n}{i,j,k,t,w}(n+w-k-t)!(-2)^i(-2)^j\binom{k+w}{k}k!(-2)^k2^{2t}

直接算复杂度 O(n4)\mathcal{O}(n^4)

由于 i,ji,j 很想，不妨令 p=i+jp=i+j 代换。

那么此时的 pp 类的贡献就像 ii 和 jj 一样，有 b2i=2ib_{2i}=2i，b2i=2i+1b_{2i}=2i+1，b2i+1=2ib_{2i+1}=2i，b2i+1=2i+1b_{2i+1}=2i+1 四种方案，同时容斥系数为 −1-1 ，于是贡献为 (−1)p22p(-1)^p2^{2p} 。

那么此时的答案：

∑p+k+t+w=n(np,k,t,w)(n+w−k−t)!(−1)p+k2k+2p+2t(k+wk)k!\sum_{p+k+t+w=n}\binom{n}{p,k,t,w}(n+w-k-t)!(-1)^{p+k}2^{k+2p+2t}\binom{k+w}{k}k!

直接枚举可以做到 O(n3)\mathcal{O}(n^3) 。

容斥好题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n,P,fac[N<<1],inv[N<<1],pw[N<<1];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
void init(int n){
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=2ll*pw[i-1]%P;
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=kpow(fac[n],P-2);
    for(int i=n-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
}
int Inv(int a){return a<=(n<<1)?kpow(a,P-2):(P-1ll*(P/a)*Inv(P%a)%P)%P;}
int main(){
    scanf("%d%d",&n,&P);
    init(n<<1);
    int ans=0;
    for(int p=0;p<=n;p++)for(int k=0;p+k<=n;k++)for(int t=0;p+k+t<=n;t++){
        int w=n-p-k-t;
        int res=1ll*fac[n]*inv[p]%P*inv[k]%P*inv[t]%P*inv[w]%P
            *pw[k+2*p+2*t]%P*fac[k+w]%P*inv[k]%P*inv[w]%P*
            fac[n+w-k-t]%P*fac[k]%P;
        (ans+=((p+k&1)?P-res:res))%=P;
    }
    printf("%lld",1ll*ans*Inv(pw[2*n])%P);
    return 0;
}