MOCK NOIP+ 20221203 日志

还是张隽恺一如既往的恶趣味。

简略题解

A – 计数

每一次遇到排列问题，我都试着建出一张 $n$ 个点 $n$ 条边的图（$x\rightarrow p_x$）后在上面思考。遗憾的是本题不能这样做。

记排列 $p$ 的逆为 $p^{-1}$，则有 $p=p^{-1}\lor (p\neq p^{-1}\land (p^{-1})^{-1}=p)$。

这是显然的：一个置换的逆元就是将其上下两行交换。故而我们可以计算出有多少个 $n$ 阶排列 $p=p^{-1}$，则 $n!$ 减去计数再除以二即为所求。

易得 $p=p^{-1}$ 的充要条件是 $p_{p_x}=x$，则可以视作每两个元素一对构成 $p_x=y,p_y=x$ 的形式，或者 $p_x=x$。记 $f(n)$ 表示 $p=p^{-1}$ 的 $n$ 阶排列数量，易得转移 $f(n)=f(n-1)+(n-1)f(n-2)$，边界有 $f(1)=1,f(2)=2$。时间复杂度 $\newcommand\bigO{\operatorname{O}}\bigO(n)$。

注意：本题条件下不一定存在 $2$ 的乘法逆元，故而记 $f'(n)$ 表示 $\frac{f(n)}{2}$ 来转移。

B – 点分治

可以发现这棵树就是树状数组展开后的样子。有 $x\ (x\in(0, 2^n))$ 的父亲为 $x-\operatorname{lowbit}(x)$。则两节点 $x,y$ 的 $\operatorname{lca}=x\ \operatorname{and}\ 2^{\log_2(x\oplus y)+1}$，即 $n$ 位二进制表示的最长公共前缀后补零。则统计固定距离的节点个数，可以钦定给定节点 $x$ 二进制表示的某一以 $1$ 结尾前缀作为最近公共祖先，后边选若干位置任填 $1$ 即可（应当减去非法情况）。

时间复杂度 $\bigO(n+\sum{k_i})$。

C – 博弈

记 $L=\sum_{i=1}^{n}l_i$。若区分每次选取的格子，可知任何一种填完恰好 $k$ 个格子后游戏结束的方案，出现的概率均为 $\frac{1}{L^{\underline{k}}}$。

我们枚举在哪一行结束了游戏，记其编号为 $i$。假若 $1\sim i-1$ 行填写了 $c_1$ 个格子（每一行均未填满），记有 $f(i-1,c_1)$ 种选择；$i+1\sim m$ 行填写了 $c_2$ 个格子，记有 $g(i+1,c_2)$ 种选择。则一共填写了 $s=c_1+c_2+l_i$ 格；又因为本题权值为拼接字符串表示的十进制数，且是“按照顺序依次填写”，则记 $h'(s,t)$ 表示按序填写 $s$ 个字符串，择取其中 $t$ 个以任意顺序摆放拼接，且第 $s$ 个字符串一定选中的权值总和。答案即 $$\sum_{i=1}^{n}\sum_{c_1=0}^{\sum_{j=1}^{i-1}l_j-1}\sum_{c_2=0}^{\sum_{j=i+1}^{n}l_j-1}\frac{f(i-1,c_1)g(i+1,c_2)(c_1+c_2)!h'(l_i+c_1+c_2,l_i)}{L^{\underline{l_i+c_1+c_2}}}$$

$f,g$ 的计算都是简单的背包，复杂度 $\bigO(n^3)$；思考如何快速计算 $h’$。

场上我试图维护“所有可能的结果字符串”的各项信息，同时直接计算暴力插入一个字串 $a_i$ 的贡献（插入后的数可以拆分成 $\text{原数更高位}\times 10^{|a_i|+|\text{原数更低位}|}+a_i\times 10^{|\text{原数更低位}|}+\text{原数更低位}$，维护每个串在所有位置劈开得到的“高位”和“低位”权值和），但发现式子首项无法用线性方式维护插入 $a_i$ 之后的贡献。

何钒佑教给我们一更聪明的贡献方法：将每一个字串的贡献独立，写作 $\sum a_i\times10^{|结果串更低位|}$。具体地，对于一个由 $t$ 个串拼接而成的的结果串，我们将其复制成 $t$ 份；对于第 $p$ 份，我们预留第 $p$ 位作为一个“窗口”，用第 $p$ 份串计算 $a_p$ 的贡献。若要将串 $a_p$ 填入，我们既可以填入窗口右侧，此时对权值积的贡献为 $10^{|a_p|}$；也可以占用窗口本身而计算 $a_p\times \sum \text{低位权值积}$；也可以填入窗口左侧，贡献不变。容易验证，它的和不重不漏地计算了每一个串的每一位代价；指数相加结果相乘，它具有结合律。于是记 $h(s,t,k,0/1)$ 表示考虑了 $a_1,\cdots,a_s$，择其中 $t$ 个拼接，且在窗口右侧已经填入 $k$ 个串，窗口是否被占用的权值总和；转移时做些处理，就能计算 $h'(s,t)$。

时间复杂度 $\bigO(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
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
115
#include <bits/stdc++.h>
using namespace std;

#define inl inline
#define scd second
#define fst first
#define empb emplace_back
#define all(p) begin (p), end (p)
using ll = long long;
using ull = unsigned long long;
using pint = pair <int, int>;

constexpr int N = 305, L = 605, P = 1e9 + 9;
int n, m, l[N], pre[N], lsum; ll a[N], len[N]; char s[N];
ll f[N][L], g[N][L], fact[L]; int c[L][L];
ll ans, aru[N][N], pow10[L], fall[L], h[N][N][2], _h[N][N][2];

inl ll fpow (ll a, ll b) {
	ll res = 1; a %= P;
	for (; b; b >>= 1) {
		if (b & 1) (res *= a) %= P;
		(a *= a) %= P;
	}
	return res;
}
inl void calc_c (int lmt) {
	for (int x = 0; x <= lmt; ++x) {
		c[x][0] = 1;
		for (int y = 1; y <= x; ++y)
			c[x][y] = (c[x - 1][y] + c[x - 1][y - 1]) % P;
	}
	fact[0] = pow10[0] = fall[0] = 1;
	for (int x = 1, _x = lsum; x <= lmt; ++x, --_x)
		fact[x] = fact[x - 1] * x % P,
		fall[x] = fall[x - 1] * fpow (_x, P - 2) % P;
	for (int x = 1; x < N; ++x)
		pow10[x] = pow10[x - 1] * 10 % P;	
}
inl void calc_f () { // f (i, j): 前 i 行选 j 个，均未占满的方案数。
	f[0][0] = 1; int lsum = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j <= lsum; ++j) {
			const ll _f = f[i][j];
			for (int k = 0; k < l[i + 1]; ++k)
				f[i + 1][k + j] += _f * c[l[i + 1]][k] % P;
		}
		lsum += l[i + 1];
		for (int j = 0; j <= lsum; ++j) f[i + 1][j] %= P;
	}
}
inl void calc_g () { // g (i, j): 后 i 行选 j 个，均未占满的方案数。
	g[m + 1][0] = 1; int lsum = 0;
	for (int i = m + 1; i > 1; --i) {
		for (int j = 0; j <= lsum; ++j) {
			const ll _g = g[i][j];
			for (int k = 0; k < l[i - 1]; ++k)
				g[i - 1][k + j] += _g * c[l[i - 1]][k] % P;
		}
		lsum += l[i - 1];
		for (int j = 0; j <= lsum; ++j) g[i - 1][j] %= P;
	}
}
inl void calc_h () { // h (i, j, k, b): a1, a2, ... ai 选了 j 个，窗口右侧选择 k 个，窗口未占/占用的方案数
	h[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		memset (_h, 0, sizeof _h);
		const ll lco = pow10[len[i + 1]];
		for (int j = 0; j <= i; ++j) {
			for (const bool b : { 0, 1 })
				for (int k = 0; k <= j; ++k) {
					const ll val = h[j][k][b];
					_h[j + 1][k + 1][b] += val * (k + 1) % P * lco % P;
					_h[j + 1][k][b] += val * (j - k - b + 1);
				}
			for (int k = 0; k <= j; ++k)
				_h[j + 1][k][1] += h[j][k][0] * a[i + 1] % P;
		}
		for (int j = 0; j <= i + 1; ++j) {
			for (int k = 0; k <= j; ++k)
				(h[j][k][0] += _h[j][k][0]) %= P,
				(h[j][k][1] += _h[j][k][1]) %= P,
				aru[i + 1][j] += _h[j][k][1];
			aru[i + 1][j] %= P; // aru (i, j): 同题解中 h'(i, j)
		}
	}
}

int main () {
	/* MOCK NOIP+ 20221203 吴秋实 */
//	freopen ("game.in", "r", stdin);
//	freopen ("game.out", "w", stdout);

	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		scanf ("%d", l + i),
		pre[i] = pre[i - 1] + l[i];
	calc_c (lsum = pre[m]);
	for (int i = 1, j; i <= n; ++i) {
		scanf ("%s", s); j = 0;
		while (s[j])
			a[i] = (a[i] * 10ll + (s[j]^48)) % P,
			len[i] = ++j;
	}
	calc_f (); calc_g (); calc_h ();
	for (int i = 1; i <= m; ++i)
		for (int k1 = 0; k1 <= pre[i - 1]; ++k1)
			for (int k2 = 0, s = k1 + l[i]; k2 <= lsum - pre[i]; ++k2, ++s)
				ans += f[i - 1][k1] * g[i + 1][k2] % P * fact[k1 + k2] % P
					* aru[s][l[i]] % P * fall[s] % P;
	printf ("%lld", ans % P);

	return 0;
}

D – 最优化

最小费用增广流。