奇偶矩阵题解

题目大意

奇偶矩阵 Tablica

Solution

这里学到了个经典小 trick：矩阵转二分图。左部是行、右部是列，如果有一条连边，则意味着这条边构成的坐标（即矩阵中的点）被选中。

那现在转化成：二分图左部 $n$ 个点、右部 $m$ 个点，在无重边的情况下，求每个点的度数 $\in [1,2]$ 的方案数。

枚举左部有 $j$ 个二度点，相当于将 $n+j$ 个球放进 $m$ 个盒子里，每个盒子球的数量 $\in [1,2]$。设 $f_{i,j}$ 表示 $i$ 个球放进 $j$ 个盒子的方案数，易得：

$$ f_{i,j}=f_{i-1,j-1}\times i+\binom{i}{2}\times f_{i-2,j-1} $$

贡献为 $\frac{f_{n+j,m}}{2^j}$，因为同一左部点代表的球本质相同。

可是有重边，枚举重边个数 $i$，容斥一下，答案为：

$$ \sum\limits_{i=0}^n \binom{n}{i}\binom{m}{i}i!(-1)^i\sum\limits_{j=0}^{n-i}\frac{1}{2^{i+j}}\binom{n-i}{j}f_{n-i+j,m} $$

可以提一个 $\frac{1}{2^i}$ 出来：

$$ \sum\limits_{i=0}^n \binom{n}{i}\binom{m}{i}i!(-1)^i\frac{1}{2^i}\sum\limits_{j=0}^{n-i}\frac{1}{2^{j}}\binom{n-i}{j}f_{n-i+j,m} $$

后面的 $\sum$ 可以写个函数封装起来。

代码

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


#include<bits/stdc++.h>
using namespace std;

#define int long long

const int P=1e9+7,N=6e3+5;

int n,m;
int fac[N],inv[N],pow2[N];
int f[N][N];

int qpow(int a,int b=P-2)
{
    int c=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1)
            c=c*a%P;
    return c;
}

void init()
{
    fac[0]=1;
    for(int i=1;i<=N-5;i++)
        fac[i]=fac[i-1]*i%P;
    inv[N-5]=qpow(fac[N-5]);
    for(int i=N-5;i;i--)
        inv[i-1]=inv[i]*i%P;
    int inv2=qpow(2);
    pow2[0]=1;
    for(int i=1;i<=N-5;i++)
        pow2[i]=pow2[i-1]*inv2%P;
}

int C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*inv[m]%P*inv[n-m]%P;
}

int work(int i)
{
    int res=0;
    for(int j=0;j<=n-i;j++)
        (res+=pow2[j]*C(n-i,j)%P*f[n-i+j][m-i]%P)%=P;
    return res;
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    init();
    f[0][0]=1;
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j-1]*i%P;
            if(i>=2)
                (f[i][j]+=f[i-2][j-1]*C(i,2)%P)%=P;
        }
    int ans=0;
    for(int i=0;i<=n&&i<=m;i++)
        (ans+=C(n,i)*C(m,i)%P*fac[i]%P*((i&1)?-1:1)*pow2[i]%P*work(i)%P)%=P;
    ans=(ans%P+P)%P;
    printf("%lld\n",ans);
    return 0;
}

奇偶矩阵 题解

题目大意

Solution

代码

奇偶矩阵题解