【泛做】RE:从零开始的计数生活

这一部分大概是整理一下自己做过的计数题?

感觉有很多题都很神(不)仙(会)。慢慢来吧…

感觉其实本质上考察的还是 dp 功底+组合技巧/能力。

总的来说,如果没有计数头脑(个人认为是可以练出来的)的人,遇到这种题一般要么是 dfs/子集枚举,要么是状压,大概是常见比赛里面 $3/5/7/10$ 这档最低的部分分…所以计数这东西如果不是天赐之才,其实是需要深入研究的吧。

等会儿,我扯这些干什么?扯这些能帮我学会计数吗?

[POJ1737] Connected Graph

$n$ 阶有标号无向连通图计数。

$n\leq 5000/3 \cdot10^5/10^6$ 。

Sol 1

考虑设 $f_n$ 表示 $n$ 个点构成的有标号无向连通图个数,$g_n$ 表示 $n$ 个点构成的有标号无向不连通图个数,$h_n$ 表示 $n$ 个点组成的图的个数,那么有

其中第三个转移是以枚举包含 $1$ 的连通块为决策步长来进行转移。大概就是什么「围绕一个基本元来转移」的思想吧。复杂度 $O(n^2)$ 。

Sol 2

考虑把原来的式子化简

然后考虑分解一下

然后就变成分治 FFT 大傻题了。复杂度 $n\log ^2n$ 。

Sol 3

考虑组合意义。如果设 $\mathbf{H}_n$ 为 $n$ 个点的图的 EGF,$\mathbf{F}_n$ 为 $n$ 个点的连通图的 EGF,那么显然有

然后就变成了牛顿迭代大傻题,复杂度 $O(n\log n)$ 。

[A Private Problem from ITMO] How many Of them?

据说是托神出的题 233

给定 $n,m$ ,求 $n$ 个点、割边 $\leq m$ 的无向连通图个数。

$n,m\leq 50$ 。

你说这种题能怎么做?那只能多做几道涨经验了。也不知道啥时候能出师…

考虑暴力 $dp$ 当然是设 $f_{n,m}$ 表示 $n$ 个点 $m$ 条割边的无向连通图个数。根据上一题里的 idea,应该枚举包含 $1$ 的边双来转移(因为统计对象改成了割边)。考虑枚举完一个边双,剩下会有数量不定的边双与当前的边双相连,于是考虑设 $g_{n,m,k}$ 表示有 $n$ 个点、$m$ 条割边,$k$ 个边双的连通图数量。那么有转移:

最后一个 $i^j$ 是考虑不同的割边连接方案。因为这个转移本质上可以看作是在一个 $n-i$ 个点、$m-j$ 条割边、$j$ 个边双的图中插入一个包含 $i$ 个点的边双。

特殊的,考虑 $f_{n,0}$ 可以直接容斥出来

其中 $\mathbf{F}_n$ 是 $n$ 个点的连通图个数。

之后考虑如何算 $g$ ,还是通过枚举一个边双来完成转移

其中 $x$ 用来计数当前边双中,拿一个点连出去一条割边。于是最后复杂度 $O(n^5)$ 。不过显然是跑不满的。

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
int ans ;
int n, m ;
int H[N] ;
int F[N] ;
int G[N] ;
int f[N][N] ;
int comb[N][N] ;
int g[N][N][N] ;

int expow(int a, int b){
int res = 1 ;
while (b){
if (b & 1)
res = (ll)res * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return res ;
}

int main(){
cin >> n >> m ; F[1] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
H[i] = expow(2, i * (i - 1) / 2) ;
for (int i = 0 ; i <= n ; ++ i) comb[i][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= i ; ++ j)
comb[i][j] = addn(comb[i - 1][j], comb[i - 1][j - 1]) ;
for (int i = 2 ; i <= n ; ++ i){
for (int j = 1 ; j < i ; ++ j){
add(G[i], 1ll * comb[i - 1][j - 1] * F[j] % P * H[i - j] % P) ;
}
F[i] = decn(H[i], G[i]) ;
}
f[1][0] = g[1][0][1] = 1 ;
//debug(G, 1, n) ;
//debug(F, 1, n) ;
/*
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= i ; ++ j)
cout << comb[i][j] << " \n"[j == i] ;
*/
for (int i = 2, s ; i <= n ; ++ i){
s = 0 ;
for (int j = 1 ; j < i ; ++ j){
for (int t, k = 1 ; k <= i - j ; ++ k){
t = 0 ;
for (int l = 1 ; l <= j ; ++ l)
add(t, 1ll * g[i - k][j - l][l] * expow(k, l) % P) ;
add(f[i][j], 1ll * t * f[k][0] % P * comb[i - 1][k - 1] % P) ;
}
add(s, f[i][j]) ;
}
f[i][0] = decn(F[i], s) ;
for (int j = 1 ; j <= i ; ++ j){
for (int k = 0 ; k <= i - j ; ++ k){
if (j == 1){
g[i][k][j] = 1ll * f[i][k] * i % P ;
continue ;
}
for (int p = 1 ; p < i ; ++ p)//连通块数
for (int q = 0 ; q <= k ; ++ q)//割边数
add(g[i][k][j], 1ll * g[i - p][k - q][j - 1] * f[p][q] % P * comb[i - 1][p - 1] % P * p % P) ;
}
}
}
for (int i = 0 ; i <= m ; ++ i)
add(ans, f[n][i]) ; return cout << ans << '\n', 0 ;
}

[BJWC2018] 最长上升子序列

现在有一个长度为 $n$ 的随机排列,求它的最长上升子序列长度的期望。$n\leq 20$ 。

其实是把数据范围改小了,原题是个打表题233

考虑观察最长上升子序列的性质。记 $h_i$ 为截止到前 $i$ 位中最长上升子序列的长度,同时设 $g_{i}=\max_{j=1}^i\{h_j\}$ ,那么可以知道

发现这个序列差分之后正好是 $01$ 串,不妨设 $\{g_n\}$ 的一阶差分是 $\{d_n\}$,于是考虑对着这个东西 $dp$ 。即设 $f_{i,s}$ 表示以 $i$ 结尾的,差分序列是 $s$ 的排列数。考虑从小向大插入每个数。假设当前的 $x$ 插在原来的串的 $i$ 和 $i+1$ 之间,那么因为 $x$ 比之前任何一个数都大,那么可以知道 $h’_{i+1}=h_i+1$ ,同时假设存在某个 $k>i$ 使得 $a_k$ 是第一个大于 $a_i$ 的数,那么可以知道根据差分,应该将 $d_k$ 置为 $0$ ,所以从大到小扫的时候不断更新即可。

于是最后复杂度 $O(2^n\cdot n^2)$ 。

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
il int expow(int a, int b){
int res = 1 ;
while(b){
if (b & 1)
res = (ll)res * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return res ;
}

int ans ;
int n, m ;
int fac[N] ;
int size[M] ;
int _bit[N] ;
int f[2][M] ;

int main(){
cin >> n ; fac[0] = 1 ;
m = (1 << n) - 1 ; f[0][0] = 1 ;
for (int i = 0 ; i <= n ; ++ i) _bit[i] = 1 << i ;
for (int i = 1 ; i <= m ; ++ i)
size[i] = size[i -(i & (-i))] + 1 ;
// debug(_bit, 1, n) ;
// debug(size, 1, m) ;
for (int d = 0, i = 0 ; i < n - 1 ; ++ i){
int t = (1 << i) - 1 ;
fill(f[d ^ 1], f[d ^ 1] + t + 1, 0) ;
for (int s = 0 ; s <= t ; ++ s){
int pos = 2333 ;
add(f[d ^ 1][s << 1], f[d][s]) ;
for (int k = i ; k >= 0 ; -- k){
int t = (s >> k) << (k + 1) ;
t |= _bit[k], t |= (_bit[k] - 1) & s ;
if (1 << k & s) pos = k ;
if (pos != 2333) t ^= _bit[pos + 1] ;
add(f[d ^ 1][t], f[d][s]) ;
}
}
d ^= 1 ;
}
for (int i = 1 ; i <= n ; ++ i)
fac[i] = (ll)i * fac[i - 1] % P ;
// debug(fac, 1, n) ;
for (int i = 0 ; i < m ; ++ i)
add(ans, (int)(1ll * f[(n - 1) & 1][i] * (size[i] + 1) % P)) ;
ans = (ll)ans * expow(fac[n], P - 2) % P ;
cout << ans << '\n' ; return 0 ;
}

[AGC002 F] Left Most Ball

给你 $n$ 种颜色的球,每个球有 $k$ 个,把这 $n\times k$ 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求有多少种不同的颜色序列,答案对 $10^9+7$ 取模。

$1\leq n, k\leq 2000$。

[AHOI2009] 中国象棋

在一个 $n$ 行 $m$ 列的棋盘上,让你放若干个炮(可以是 $0$ 个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。

$1\leq n,m\leq 100$。

[CQOI2011] 放棋子

在一个 $m$ 行 $n$ 列的棋盘里放一些颜色在 $1\sim c$ 之间的棋子,使得每个格子最多放一个棋子,且不同颜色的棋子不能在同一行或者同一列,有多少种方法?

$1\le n,m\le 30$,$1\le c\le 10$,总棋子数 $\le \min(250,n\times m)$。

[ARC074C] RGB Sequence

有一个序列 $\left\{a_{n}\right\}$,要给序列中的每个元素一种颜色:红/绿/蓝。有 $m$ 条限制 $(l,r,x)$,表示格子 $l\sim r$ 中颜色的种类数要恰好为 $x$,问可行的方案数。

$ 1\leq n,m\leq 300 $ 。

[ARC071D] Infinite Sequence

定义 $n-$可爱序列 指无限长的由 $\{1,2…,n\}$ 组成的序列。同时 $a_1,a_2…$满足以下条件:

1.第 $n$ 个及以后的元素是相同的,即若 $\forall i,j\geq n,a_i=a_j$ 。

2.对于每个位置 $i$,紧随第 $i$ 个元素后的 $a_i$ 个元素是相同的,即若 $\forall i<j<k≤i+a_i,a_j=a_k$。

输入 $n$,请输出 $n-$可爱序列的数量 $\bmod 10^9+7$ 。

$n\leq{10^6}$。

[LuoguP5464] 缩小社交圈

社交圈子里有 $n$ 个人,每个人都有一个 SAN 值范围 $[l_i,r_i]$。当两个人的 SAN 值交集不为空时,这两个人有 PY 关系。

现在希望从社交圈子里面挑选出一些人组成一个集合 $S$,如果将所有集合内的人中有 PY 关系的那一对人都连上边,则 $S$ 刚好成为一个树(森林不行哦)。

请问,有多少种可以选择的方案?由于答案可能很大,请对 $10^{9}+7$ 取模。

$1\leq n\leq 2000,1\leq l_i,r_i\leq 4000$ 。

[LuoguP5241] 序列

构建一个 $n$ 个点的有向图 G,初始没有任何边。

接下来构建一个长度为 E 的边的序列 A,序列中每条边都是满足 $1≤s,t≤n$ 且 $s≠t$ 的有向边 $(s,t)$,且序列中的边互不相同。按照顺序把这些边加入到 G 中,每次加入后计算当前图的强连通分量个数并记录下来,得到一个新的长度为 E 的正整数序列 B。如果两个边的序列得到的 B 相同则称它们本质相同。

请问有多少种本质不同的边的序列,

$1\leq n\leq 400$ 。

[SDOI2010] 地精部落

传说很久以前,大地上居住着一种神秘的生物:地精。地精喜欢住在连绵不绝的山脉中。具体地说,一座长度为 $N$ 的山脉 $H$ 可分为从左到右的 $N$ 段,每段有一个独一无二的高度 $H_i$ ,其中 $H_i$ 是 $1$ 到 $N$ 之间的正整数。如果一段山脉比所有与它相邻的山脉都高,则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉,其他都有两段(即左边和右边)。类似地,如果一段山脉比所有它相邻的山脉都低,则这段山脉是一个山谷。

地精们有一个共同的爱好——饮酒,酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸,地精美酒的香味可以飘到方圆数里的地方。

地精还是一种非常警觉的生物,他们在每座山峰上都可以设立瞭望台,并轮流担当瞭望工作,以确保在第一时间得知外敌的入侵。地精们希望这 $N$ 段山脉每段都可以修建瞭望台或酒馆的其中之一,只有满足这个条件的整座山脉才可能有地精居住。

现在你希望知道,长度为 $N$ 的可能有地精居住的山脉有多少种。两座山脉 $A$ 和 $B$ 不同当且仅当存在一个 $i$,使得 $A_i≠B_i$。由于这个数目可能很大,你只对它除以 $P$ 的余数感兴趣。

对于 $100\%$ 的数据,满足 $3≤N≤4200$,$P≤10^9$。

大概就是说要计数这样的 $n-$排列 :连续上升/下降段长度不超过 $2$ 。

[POJ1037] A decorative fence

定义 n decorative Fence 为一段这样的 $1\sim n$ 排列 $\{a_n\}$ :

$\forall i\in [2,n-1]$ :

给定 $n,k$ ,求字典序第 $k$ 大的 n decorative Fence

$n,T\leq 500$ 。

这大概是一类计数题,叫做凑排列题。大概就是套了一个构造方案的计数。

观察这题性质,发现对于一个排列,其关键性质在于最后整个序列的元素集合给定,且保证每个位置的数两两不同,所以本质上并不关心每个数到底是多少,只关心在某个子状态里面每个数产生了多少贡献。

于是考虑 $f_{i,j,0/1}$ 表示 $i$ 个 Fence 里面,当前最左/右边的在这 $i$ 个里面排名第 $j$ 小,处于高位/低位的方案数。于是有转移。

转移的逻辑顺序是从小到大插入每个数。注意一个很有趣的细节,就是「之前序列(即长度为 $i-1$ 的序列)中的第 $k$ 小一定比多了一个数之后序列(即长度为 $i$ 的序列)的第 $k$ 小要大」,证明可以考虑插入这个数之后,$1\sim k-1$ 号数字位置不变,所以原来的 $k$ 号只能后移一位给新加进来的数让出位置。

然后构造。为了保证字典序最小,只需要从小到大贪哪个状态合法即可。考虑如果已经考虑了前 $i$ 个位置,当前选了 $x$,高低状态为 $y$,那么如果 $f_{n-i+1,x,y} \geq k$ 的话,说明这意味必然要选择 $x$ ,否则将 $k$ 减掉当前的方案数。不难知道这样做是对的。

注意如果是贪心的话,应该先考虑 $y=1$ 再考虑 $y=0$ 。于是最后复杂度 $O(n^3+Tn^2)$ 。

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

int T ;
int ans[N] ;
int n, h, p ;
bool vis[N] ;
ll f[N][N][2], k ;

int main(){
cin >> T ;
f[1][1][1] = f[1][1][0] = 1 ;
for (int i = 2 ; i < N ; ++ i)
for (int j = 1 ; j <= i ; ++ j){
for (int o = j ; o < i ; ++ o)
add(f[i][j][0], f[i - 1][o][1]) ;
for (int o = j - 1 ; o >= 1 ; -- o)
add(f[i][j][1], f[i - 1][o][0]) ;
}
while (T --){
h = 0, p = 0 ; n = qr(), k = qr() ;
for (int i = 1 ; i <= n ; ++ i) vis[i] = 0 ;
for (int i = 1 ; i <= n ; ++ i){
if (f[n][i][1] >= k) { h = i, p = 1 ; break ; } else k -= f[n][i][1] ;
if (f[n][i][0] >= k) { h = i, p = 0 ; break ; } else k -= f[n][i][0] ;
}
vis[h] = 1 ; ans[1] = h ;
for (int i = 2, o ; i <= n ; ++ i, p ^= 1){
if (!p){
o = 0 ;
for (int j = 1 ; j <= h ; ++ j) if (!vis[j]) ++ o ;
for (int j = h + 1 ; j <= n ; ++ j){
if (vis[j]) continue ; ++ o ;
if (f[n - i + 1][o][1] >= k){
vis[ans[i] = h = j] = 1 ; break ;
}
else k -= f[n - i + 1][o][1] ;
}
}
else {
o = 0 ;
for (int j = 1 ; j <= h - 1 ; ++ j){
if (vis[j]) continue ; ++ o ;
if (f[n - i + 1][o][0] >= k){
vis[ans[i] = h = j] = 1 ; break ;
}
else k -= f[n - i + 1][o][0] ;
}
}
}
debug(ans, 1, n) ;
}
}

[Luogu2017.Mar.Round2] 小清新签到题

给定自然数 $n$、$k$、$x$,你要求出第 $k$ 小的长度为 $n$ 的逆序对对数为 $x$ 的 $1\sim n$ 的排列 $a_1,a_2 … a_n$。

$n\leq 300,k\leq 10^{18}$。

大概是和上个题差不多的?也是凑排列题。

然后考虑设 $f_{i,j,k}$ 表示剩 $i$ 个数,最左边的数在里面排名为 $j$ ,逆序对数为 $k$ 的方案数。那么转移就是

说实话到这里我本来觉得我把这题给秒了。

然后发现凑方案数的话,就只需要枚举每个位置的数是多少即可,这样最终复杂度就是 $O(n^3x)$,并不能过。发现可以前缀和优化一波,最后复杂度就变成了 $O(n^2x)$ 的了。虽然依旧并不可以过得去,但是似乎极限数据跑的也不是慢到直接出不来结果(指20s之内能跑出来),空间也不是大到本机开不下(指 ML = 3801.04 MiB )

代码大概是:

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
int len[N] ;
int ans[N] ;
int rk, rst ;
int n, m, x ;
bool vis[N] ;

ll w ;
ll g[2][M] ;
ll* f[N][N] ;

int main(){
cin >> n >> w >> x ;
m = (n * (n - 1)) >> 1 ; g[1][0] = 1 ;
f[1][1] = new ll[1] ; f[1][1][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
len[i] = min(x, i * (i - 1) / 2) ;
for (int i = 2, d = 0 ; i <= n ; ++ i){
fill(g[d], g[d] + m + 1, 0) ;
for (int j = 1 ; j <= i ; ++ j){
f[i][j] = new ll[len[i] + 1] ;
for (int k = j - 1 ; k <= len[i] ; ++ k){
if (k - (j - 1) > len[i - 1]) break ;
f[i][j][k] = g[d ^ 1][k - (j - 1)] ;
if (g[d][k] < w) g[d][k] += f[i][j][k] ;
}
}
d ^= 1 ;
}
ll _limit = 0 ;
for (int i = 1 ; i <= n ; ++ i)
_limit += 1l * i * len[i] ;
cout << "ML = " << (4 * (ldb)_limit / 1024 / 1024) << " MiB \n" ;
for (int i = 1 ; i <= n ; ++ i){
for (int j = 1, o ; j <= n ; ++ j){
if (vis[j]) continue ; o = 0 ; int t = 0 ;
for (int k = 1 ; k <= j ; ++ k) o += (!vis[k]) ;
if (f[n - i + 1][o][x] < w) w -= f[n - i + 1][o][x] ;
else { vis[ans[i] = j] = 1 ; x -= (o - 1) ; break ; }
}
}
memset(vis, 0, sizeof(vis)) ;
debug(ans, 1, n) ; return 0 ;
}

然而我还是和这个做法鏖战了很久…企图卡过去…想了半天都不知道该怎么卡,然后卡了一个小时卡自闭了才觉得要「再您🐎的见」。

但是似乎不难发现,中间有很多状态都是没用的,即存在大量的状态都不会被最后用上,只是单纯的作为一个中间量传递方案数。冷静思考了一下,似乎不需要记录第二维。因为第二维应该填多少和第三维逆序对数之间的关系是确定的。于是重新定义状态,$f_{i,k}$ 表示 $i$ 个数有 $k$ 个逆序对的方案数,那么转移就考虑在最左端插入第 $1\sim i$ 小的这些数,即

发现同样可以前缀和优化做到 $O(nx)$ 。

之后考虑如何构造方案。发现对于一个 $n$ 位的、逆序对数量为一个确定值 $x$ 的序列,只需要知道当前位选什么,就可以知道之后的逆序对数量从而知道之后的信息。那么即只需要魔改一下,依旧是从小到大对字典序贪心即可。复杂度 $O(nx+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
37
int len[N] ;
int ans[N] ;
int rk, rst ;
int n, m, x ;
bool vis[N] ;

ll w ;
ll f[N][M] ;
ll g[2][M] ;

int main(){
cin >> n >> w >> x ;
f[1][0] = 1 ; g[1][0] = 1 ;
m = min((n * (n - 1)) >> 1, x) ;
for (int j = 1 ; j <= m ; ++ j)
g[1][j] += g[1][j - 1] ; f[0][0] = 1 ;
for (int i = 2, d = 0 ; i <= n ; ++ i){
fill(g[d], g[d] + m + 1, 0) ; ll s ;
for (int j, k = 0 ; k <= m ; ++ k){
j = max(0, k - i + 1), s = 0 ;
if (!j) s = g[d ^ 1][k] - 0 ;
else s = g[d ^ 1][k] - g[d ^ 1][j - 1] ;
g[d][k] += (f[i][k] = (s > w) ? w + 1 : s) ;
if (k >= 1) g[d][k] += g[d][k - 1] ;
}
d ^= 1 ;
}
for (int i = 1 ; i <= n ; ++ i){
for (int j = 1, o ; j <= n ; ++ j){
if (vis[j]) continue ; o = 0 ; int t = 0 ;
for (int k = 1 ; k < j ; ++ k) o += (!vis[k]) ;
if (f[n - i][x - o] < w) w -= f[n - i][x - o] ;
else { vis[ans[i] = j] = 1 ; x -= o ; break ; }
}
}
debug(ans, 1, n) ; return 0 ;
}