还是张隽恺一如既往的恶趣味。
简略题解
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)$，常数大。
#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 – 最优化
最小费用增广流。
发表回复