题解 U534157 【矩阵革命】

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟

题目链接：矩阵革命。

关于题目：作为 T4，稍难的计数题。

应用算法：图论，容斥，组合数学，逆元，dp计数。

\(\qquad\!\!\)首先说一句，这道题的 \(idea\) 并不来自《黑客帝国》，只是一个题目背景。出题人的思路来自在做 P4306 [JSOI2010]连通数 这道题输出 \(n^2\) 得 \(90\) 分之后的思考：为什么概率这么大？对于一定的 \(n\) 的连通数为 \(n^2\) 的概率可不可以计算呢？

下面进入正题：

  • 一、分析题意：

\(\qquad\!\!\)这个题目描述稍显复杂，我们先来分析一下：

  1. 题目中所述的矩阵即为邻接矩阵，矩阵中的每个元素为 \(0\) 和为 \(1\) 的概率相同。
  2. 这 \(n\) 个人中任意两人彼此之间都有从对方到自己和从自己到对方的意识连接，代表所有人在一个强连通分量中。
  3. 题目所求的概率即为：对于 \(n\) 个点的有向图（没有重边，但是可能有自环），其所有点均在同一个强连通分量中的概率。
  • 二、计算过程：

\(\qquad\!\!\)首先，由于矩阵中每个元素为 \(0\) 和为 \(1\) 的概率相同，这个概率即可化为对于 \(n\) 个点的有向图（没有重边，但是可能有自环）为一个强连通图的方案数与所有\(n\) 个点的有向图（没有重边，但是可能有自环）的方案之比。

\(\qquad\!\!\)其次，我们先统计一下后者：由于这个邻接矩阵共有 \(n^2\) 个元素，每个元素只有两种情况 \(0/1\)，我们可以设\(s_n\) 表示有 \(n\) 个点的有向图的总数，即 \(s_n=2^{n^2}\)。

\(\qquad\!\!\)再次，我们先统计一下前者：

\(\qquad\!\!\)为了得到答案，我们设 \(f_n\) 表示有 \(n\) 个点的有向图为一个强连通图的总方案数。（\(f_0=0\)）

\(\qquad\!\!\)这东西不会直接求，那么我们考虑一下容斥吧： \(f_n=s_n-\) 没有组成一个强连通图的方案数。

\(\qquad\!\!\)没有组成一个强连通图的方案数又要怎么求呢？我们先把其它所有的方案数都列举出来吧：设 \(g_{n,m}\) 表示 \(n\) 个点的有向图构成 \(m\) 个强连通分量的方案数。

\(\qquad\!\!\)我们尝试对 \(f_n\) 进行一次计数，需要枚举没有组成一个强连通图的方案数：枚举其中 \(k\) 个点组成新的出度为 \(0\) 的强连通分量的方案，那么 \(k\in[0,n]\)；对于每次选取 \(k\) 个点的方案，我们可以利用组合数得出为 \(\dbinom{n}{k}\)；对于这 \(k\) 个点和剩余的 \(n-k\) 个点之间连边，情况共有 \(2^{n\times(n-k)}\) 种方案；对于我们不进行枚举的 \(n-k\) 个点，直接统计所有情况 \(s_{n-k}\)；对于我们枚举的 \(k\) 个点，利用 \(g\) 去计算方案，不过这里由 \(g_{k,m}\) 的定义和我们要枚举的是 \(k\) 个点组成新的出度为 \(0\) 的强连通分量的方案可知，在进行枚举的时候，并不是对 \(g_{k,m}\) 进行简单的加和，而是需要奇加偶减地容斥一下再计算的 \(\sum\limits_{m=1}^k (-1)^{m-1} g_{k,m}\)（出题人在推这个的时候卡了好久才想明白竟然要容斥，还特意复习了一下容斥的内容/wul）。

\(\qquad\!\!\)综上，我们可以得到一个式子：

\(f_n=s_n-\sum\limits_{k=0}^n \dbinom{n}{k}\times 2^{k(n-k)}\times s_{n-k}\times \sum\limits_{m=1}^k(-1)^{m-1} g_{k,m}\)

\(\qquad\!\!\)但是这个式子是错的……无论怎么算 \(f_n\) 都得 \(0\)。我们考虑一下错在了哪里，发现在枚举的过程中并没有排除前 \(k\) 个点和后 \(n-k\) 个点之间合成了一个强连通分量的方案，我们需要再加上 \(f_n\) 才能使等式成立：

\(f_n=s_n-\sum\limits_{k=0}^n \dbinom{n}{k}\times 2^{k(n-k)}\times s_{n-k}\times \sum\limits_{m=1}^k(-1)^{m-1} g_{k,m}+f_n\)

\(\qquad\!\!\)但是这样的式子直接就把 \(f_n\) 消掉了，我们没法得出它的值呀。但是我们还是化简一下，至少能得到一个和 \(g\) 有关的式子：

\(\sum\limits_{k=0}^n \dbinom{n}{k}\times 2^{k(n-k)}\times s_{n-k}\times \sum\limits_{m=1}^k(-1)^{m-1} g_{k,m}=s_n\)

\(\qquad\!\!\)发现在这个式子以及上面的式子中，和 \(g\) 有关的部分前面的系数只是统一的容斥系数，那么我们可以再设一个 \(h_n=\sum\limits_{m=1}^n (-1)^{m-1}g_{n,m}\) 以便计算：

\(\because\ \ h_0=0\\ \therefore \sum\limits_{k=1}^n \dbinom{n}{k}\times 2^{k(n-k)}\times s_{n-k}\times h_k=s_n\)

\(\qquad\!\!\)观察这个式子发现，\(h_n\) 似乎能有一个递推式，我们把当 \(k=n\) 的情况提出来，计算一下它的系数为 \(\sum\limits_{k=1}^n \dbinom{n}{k}\times 2^{k(n-k)}\times s_{n-k}=1\)。好巧欸，那么，化简一下原式：

\(s_n-\sum\limits_{k=1}^{n-1} \dbinom{n}{k} \times2^{k(n-k)}\times s_{n-k}\times h_k=h_n\)

\(\qquad\!\!\)这样，我们就通过尝试对 \(f_n\) 进行计数得到了 \(h_n\) 的递推式：

\(h_n=s_n-\sum\limits_{k=1}^{n-1} \dbinom{n}{k} \times2^{k(n-k)}\times s_{n-k}\times h_k\)

\(\qquad\!\!\)既然得到了 \(h_n\) 的递推式，我们想要得到有关 \(f_n\) 的式子就可以从 \(h_n\) 和 \(f_n\) 的关系上下手：我们再枚举 \(k\) 个点并且保证这 \(k\) 个点构成一个强连通分量，其余的 \(n-k\) 个点即为 \(h_{n-k}\)。这次倒是很顺利地得到了式子：

\(h_n=f_n-\sum\limits_{k=1}^n\dbinom{n-1}{k-1}\times f_k\times h_{n-k}\)

\(\qquad\!\!\)可能有人会问，为什么中间是减号呢？那是因为我们枚举的 \(k\) 个点构成了一个强连通分量，由于 \(h_n\) 是由 \(g_{n,m}\) 容斥而来，在枚举的过程中突然多加了一个强连通分量，其容斥系数自然要变化，这个变化为容斥系数为 \(-1\) 的偶数次幂则变为奇数次幂，反之则变为偶数次幂，就相当于乘了一个 \(-1\)，我们把想法上的 \(+\) 变为 \(-\) 即可。

\(\qquad\!\!\)因为 \(h_0=0\)，我们还可以把这个式子再化简一下：

\(h_n=f_n-\sum\limits_{k=1}^{n-1}\dbinom{n-1}{k-1}\times f_k \times h_{n-k}\)

\(\qquad\!\!\)终于看到了胜利的曙光，我们移项一下即可得到 \(f_n\) 的递推式：

\(f_n=h_n+\sum\limits_{k=1}^{n-1}\dbinom{n-1}{k-1}\times f_k \times h_{n-k}\)

\(\qquad\!\!\)最后，我们利用上述统计一下答案：\(ans=\dfrac{f_n}{s_n} \bmod p\)

  • 三、代码（码风不喜勿喷）：
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
const int M=19999999;
const int N=2410;
using namespace std;
int n;
int fact[N],finv[N];
//取模意义下的阶乘和阶乘逆元，用来计算组合数。
int f[N],h[N];
//上述的 f 和 h。
in int qread()
//快读
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
//快写
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in int qpow(re int x,re int y)
//快速幂
{
	int res=1;
	while(y)
	{
		if(y&1)
		{
			res=(res*x)%M;
		}
		x=(x*x)%M;
		y>>=1;
	}
	return res;
}
in int s(re int x)
//计算s(x)。
{
	return qpow(2,x*x);
}
in int C(re int x,re int y)
//计算组合数。
{
	return ((fact[x]*finv[x-y])%M*finv[y])%M;
}
signed main()
{
	n=qread();
    //读入。
	fact[0]=1;
	finv[0]=1;
	for(re int i=1;i<=n;i++)
	{
		fact[i]=(fact[i-1]*i)%M;
	}
	finv[n]=qpow(fact[n],M-2);
	for(re int i=n-1;i>=1;i--)
	{
		finv[i]=(finv[i+1]*(i+1))%M;
	}
    //O(n)计算阶乘及其逆元。
	for(re int i=1;i<=n;i++)
	{
		h[i]=s(i);
		for(re int j=1;j<i;j++)
		{
			h[i]=((h[i]-(((C(i,j)*qpow(2,j*(i-j)))%M*s(i-j))%M*h[j])%M)%M+M)%M;
		}
	}
    //O(n^2)递推求 h。
	for(re int i=1;i<=n;i++)
	{
		f[i]=h[i];
		for(re int j=1;j<i;j++)
		{
			f[i]=(f[i]+((C(i-1,j-1)*f[j])%M*h[i-j])%M)%M;
		}
	}
    //O(n^2)递推求 f。
	qwrite((f[n]*qpow(qpow(2,n*n),M-2))%M);
	putchar('\n');
    //计算答案并输出。
	return 0;
}
aMkWY8.png
aMkRFf.png