「雅礼集训 2017 Day2」B

当然还是没有题目地址呀 QAQ
我太弱了,表示这道题目想了很久才想明白题解中的方法呀,真的很巧妙呀!
在 chrt 学姐的帮助下终于明白了,大概这次写的有点多,中间可能有描述不恰当和错误的地方,欢迎捉虫 QAQ

描述

考虑一个 $n \times n$ 的 $01$ 矩阵,计算出所有满足每一行和每一列 $1$ 的个数都是 $2$ 的矩阵个数。
设对于 $n$ 的答案为 $f_{n}$,你需要输出 $\sum_{i = 1}^{n}f_{i}$,答案对 $998244353$ 取模。

对于 $10 \%$ 的数据,满足:$n \leq 7$
对于 $20 \%$ 的数据,满足:$n \leq 50$
对于 $30 \%$ 的数据,满足:$n \leq 150$
对于 $40 \%$ 的数据,满足:$n \leq 500$
对于 $70 \%$ 的数据,满足:$n \leq 10000$
对于 $100 \%$ 的数据,满足:$n \leq 10^{7}$

分析

对于$70 \%$的数据

看数据范围大概是一个DP,Orz坐我旁边的大爷
DP 的思路大概是这样的:
我们定义 $dp[i][j]$ 为还剩 $i$ 列没有填过 $1$,$j$ 列只填了一个 $1$。
那么我们有转移方程

这三种转移都是在一行中选两个,其实可以用滚动数组来滚动一下。

  • $\binom{2}{i} \cdot dp[i - 2][j + 2]$ 表示在 $i$ 个没有填过 $1$ 的列中选两个,然后 $i$ 少了两个 $j$ 多了两个
  • $i \cdot j \cdot dp[i - 1][j]$ 表示在 $i$ 个没用的列中选一个,在 $j$ 个填过一个 $1$ 的列中选一个,那么$i$减少了一个 $j$ 增加了一个又减少了一个没变
  • $\binom{2}{j}dp[i][j - 2]$ 相当于在 $j$ 个填过一个 $1$ 的列中选两个,所以 $j$ 少了两个而 $i$ 没有变

因为这是一个自上而下的 DP,而 $dp[i][0]$ 表示的是”目前到达这个状态,把它填完的方案数”,而不是”到达这个状态的方案数”,所以最后答案可表示为:

对于$100 \%$的数据

其实这道题目的本质大概就是OEIS A001499
题解中满分的思路大概是这样的:
题解中是这样描述的将同一行和同一列之间的$1$连边,那么我们将$01$矩阵转化为一个二分图,如图所示:

转化为二分图之后,考虑一个左边和右边各有$n$个点的二分图,如上图的合法方案中,左边和右边的任意两点之间有边,也就是说原题的合法方案相当于这个二分图中的多重完美最大匹配,那么也就是说原题中的答案转化成为了求二分图中多重完美最大匹配的数量。而这个多重完美最大匹配长什么样呢? 是一堆分离的环

于是我们枚举 $1$ 号点所在的环的大小,删掉这个环,然后我们得到了一个更小的二分图,就这样我们得到了比原问题更小的子问题,然后建立递推关系:
    我们令 $f_{n}$ 为在 $n \times n$ 的矩阵中满足题目条件的方案数,因为最后是要计算所有方案的和,与其最后在相加一遍,不如现在直接计入答案中,那么,我们有递推式:

这个递推式怎么来理解呢QAQ,大概是这样的:
我们把二分图中一个大小为 $2i$ 的环分为几部分来看待:$1$ 号点 + 左边剩下的 $(i - 1)$ 个点 + 右边的 $i$ 个点。所以选出一个环有 $\binom{i}{n}\cdot \binom{n - 1}{i - 1} $ 种方法;那么 $A_{n}$ 是什么呢,就是这个环的连边方法。那么到此为左边和右边都只剩下 $(n - i)$ 个点了,那么这就是一个子问题 $f_{n - i}$。把它们乘起来那么我们就得到了 $1$ 号点所在的环的大小为 $2i$ 的所有方案数了。

$A_{n}$ 是这个环的连边方法,我们可以把这个问题等价为:对于一个 $n \times n$ 的矩阵中有且仅有一个环的方案数我们称之为$A_{n}$,那么有:

这一部分其实比较好理解,就是先将每一行每一列放置一个 $1$ 的方案数为 $n!$,令 $p_{i}$ 为第 $i$ 行所在的 $1$ 所在的列编号,那么在 $p_{1}$ 列放的第二个 $1$ 的方案数就为 $n - 1$;令 $p_{1}$ 列第二个 $1$ 所在的行编号为 $q_{i}$,那么在 $p_{q_{i}}$ 列放置第 $2$ 个 $1$ 的方案数为 $n - 2$,然后 $n - 3 \cdots$。可以自己换画一个 $4 \times 4$ 的图意会一下,因为这个过程被计算了两次(逆过程也被计算了一次),所以最后除以 $2$。

仅仅有递推式也是很难得到满分的,$n = 10^{7}$ 意味着我们最好在 $\Theta(n)$ 的时间复杂度中算出来,$\Theta(nlogn)$ 一样会超时,那么我们对式子进行如下的变换:

现在等式两边同时除以 $(n!)^{2}$,那么有:

令 $g_{n} = \frac{f_{n}}{(n!)^{2}}$,那么 $f_{n} = g_{n} \cdot (n!)^{2}$,所以原式变为:

那么我们现在只需要处理出逆元然后维护 $g_{n}$ 的前缀和,线性扫一遍就可以了,时间复杂度 $\Theta(n)$。

代码

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
//「雅礼集训 2017 Day2」B
//2017/7/4
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 10000000 + 3;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int n;
ll fac[MAX_N], inv[MAX_N];//阶层,阶层的逆元
ll ans;

inline ll exgcd(ll a, ll b, ll &x, ll &y){
if(b == 0) {x = 1, y = 0;}
else{
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
}

inline ll calculate(ll a, ll b){//计算逆元
ll x = 0, y = 0;
exgcd(a, b, x, y);
return (x % b + b) % b;
}

inline void prepare(){
// printf("%d\n", n);
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;
// for(int i = 1; i <= n; ++i) printf("f[%d] = %lld\n", i, fac[i]);
inv[n] =calculate(fac[n], MOD);
// printf("%lld\n", inv[n]);
for(int i = n - 1; i >= 0; --i) inv[i] = (ll)inv[i + 1] * (i + 1) % MOD;
// for(int i = 1; i <= n; ++i) printf("inv[%d] = %lld\n", i, inv[i]);
}

int main()
{
n = readIn();
// printf("%d\n", n);
prepare();

ans = 0;
ll preg = 1, lastg = 0, divided = calculate(2, MOD);
for(int i = 2; i <= n; ++i){
ll tmpg = (ll)preg * divided % MOD * inv[i] % MOD * fac[i -1] % MOD;
(ans += (ll)tmpg * fac[i] % MOD * fac[i] % MOD) %= MOD;
(preg += lastg) %= MOD;
lastg = tmpg;
}
printf("%lld\n", (ans % MOD + MOD) % MOD);
return 0;
}

参考

chrt学姐的博客很赞 =w=

Partager