做题记录

· · 算法·理论

本来在小号上，记着不方便，就扒到大号上来。

CF1201C

给定若干个数。可以进行 n 次单点加操作，求中位数的最大值。

二分答案，每次 O(n) check 即可。

CF1183C

多组询问。每一次查询给出四个数字：k, n, a, b。

你在一个回合里面可以选择以下两种操作：

问在完成了 n 个回合之后，且 k>0 的前提下，最终答案的最大值。

可以直接数学题解个不等式，但是我沙比写了二分。

二分 -a 的次数，剩下减 b 的次数 n - mid。check 一下是不是小于 0 就行了。

\text{AC code}

CF920G

给定 x, p, k。求 > x 的第 k 小的与 p 互质的数。

首先，发现答案具有可二分性。二分答案，发现问题转化为：求 \sum \limits_{i = 1}^{n}[(i, p) = 1]。

对这个式子进行莫反变形：

\sum_{i = 1}^{n} [(i, p) = 1] = \sum_{i = 1}^{n} \sum_{d | (i, p)}^{} \mu(d) = \sum_{d | p}^{} \mu(d) \sum_{i = 1}^{\frac{n}{d}} 1 = \sum_{d | p}^{} \mu(d) \left \lfloor \dfrac{n}{d} \right \rfloor

筛出 \mu 之后这个东西可以直接 O(d(p)) 的复杂度算。

时间复杂度 $O(\max \{p\} + T d(p) \log V)$。 ## CF140C 给定 $n$ 个半径为 $r_i$ 的球。要求选出至多的三元组，使得三元组中的球半径两两不等。 考虑贪心。每个球按照出现次数排序扔到优先队列里去。每次取出出现次数最多的三个凑成一个三元组即可。时间复杂度 $O(n \log n)$。 [$\text{AC code}$](https://www.luogu.com.cn/record/132040225) ## CF898E 给定 $n$ 个数，每次操作可以加一或者减一。求将序列变成 $\dfrac{n}{2}$ 个完全平方数，剩下的都是非完全平方数的最小操作次数。 思路：找到每个值变成临近完全平方数的最小代价。然后根据代价排序，将前一半变成完全平方数。剩下变成非完全平方数，只需要加一即可。（当 $a_i = 0$ 时要加二）。 [$\text{AC code}$](https://www.luogu.com.cn/record/132045764) ## CF888C 求最大的 $k$ 值，使得存在一个字符 $c$ 在文本串 $s$ 的每个长度为 $k$ 的子串中都出现过。 二分答案，设答案为 $k$，用类似双指针的思想跑一遍文本串进行 `check`。时间复杂度 $O(n S \log n)$，其中 $S$ 表示字符集大小。 [$\text{AC code}$](https://www.luogu.com.cn/record/132053992) ## P1730 最小密度路径 题解全是 $n ^ 3 m$ $floyd$ 科技。但是分数规划显然更好想。 二分答案 $d$，检验的时候把所有边权减去 $d$，再看看 $s \to t$ 的路径长度是否小于零。 据说有向无环图 $\text{spfa}$ 不好卡。所以复杂度 $O(n ^ 2 (n + m) \log \frac{V}{\epsilon}) \sim O(1)$。 [$\text{AC code}$](https://www.luogu.com.cn/record/135423343) ## P1841 [JSOI2007] 重要的城市 显然，一个点是重要的城市，当且仅当存在 $a, b, a \ne b$，从 $a$ 到 $b$ 的最短路全部经过这个点。所以理所应当 $\forall a, b$ 统计从 $a$ 到 $b$ 的最短路方案数。设为 $f_{a, b}$。如果对于点 $c$，存在 $f_{a, c} \times f_{c, b} = f_{a, b}$，并且 $a \to c \to b$ 恰好是最短路，则 $c$ 为重要城市。 由于点数很少，可以直接用 $\text{floyd}$。 [$\text{AC code}$](https://www.luogu.com.cn/record/135434167) ## P1989 无向图三元环计数 喵喵题。 摒弃根号做法，世界属于 bitset。 考虑暴力做法：枚举每条边，端点 $u, v$，找到 $w$，使得 $\left \langle w, u \right \rangle, \left \langle w, v \right \rangle \in E$。$w$ 贡献为 $1$。复杂度 $O(nm)$。这个过程可以直接用 bitset 优化。也就是记一下 $u, v$ 出边的点集，按位与一下。 但是空间开不下。可以参考三维偏序里面 bitset 的做法，直接按度分块。空间瞬间压缩成了 $O(\dfrac{n \sqrt m}{w})$。轻松跑过。 ```cpp rep(i, 1, n) { t &= 0; for (int j : E[i]) t.set(j); if (d[i] >= B) bit[id[i] = ++ cnt] = t; for (int j : E[i]) if (j < i) { if (id[j]) ans += (bit[id[j]] & t).count(); else for (int k : E[j]) ans += t[k]; } } ``` ## P2169 正则表达式 懒得写代码了。简单题。 缩点。然后跑最短路。完了。 算了水蓝还是写写吧。 [$\text{AC code}$](https://www.luogu.com.cn/record/135448185) ## P3907 圈的异或 嘴巴一下。考虑拆位。第 $k$ 次将边权重赋位 $w_i$ 的二进制第 $k$ 位。然后把 $0$ 的位缩点，把 $1$ 的位保留。二分图染色即可。 如果不想写缩点啥的，其实可以直接 $\text{floyd}$。 时间复杂度 $O((n + m) \log V) / O(n ^ 3 \log V)$。 提供一个 $\text{floyd}$ `check` 部分的实现： ```cpp bool check(int w) { memset(f, 0, sizeof f); rep(i, 1, n) rep(j, 1, n) if (~g[i][j]) f[i][j][(g[i][j] >> w) & 1] = 1; rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) if ((i ^ j) && (j ^ k) && (i ^ k)) { f[i][j][0] |= (f[i][k][0] & f[k][j][0]); f[i][j][0] |= (f[i][k][1] & f[k][j][1]); f[i][j][1] |= (f[i][k][1] & f[k][j][0]); f[i][j][1] |= (f[i][k][0] & f[k][j][1]); } rep(i, 1, n) rep(j, 1, n) if (i ^ j) { if (f[i][j][0] && f[j][i][1]) return true; if (f[i][j][1] && f[j][i][0]) return true; } return false; } ``` ## P2245 星际导航 简单题。典题。 求出原图的最小生成树，询问即为路径最大值。 可以直接倍增维护出来。注意询问两点不在同一颗树里的情况。注意森林需要每个根 dfs 一遍。 ```cpp void init() { rep(j, 1, 20) rep(i, 1, n) fa[i][j] = fa[fa[i][j - 1]][j - 1]; rep(j, 1, 20) rep(i, 1, n) f[i][j] = max(f[i][j - 1], f[fa[i][j - 1]][j - 1]); } int query(int u, int v) { int ans = 0; if (dep[u] < dep[v]) swap(u, v); dep(i, 20, 0) if (dep[fa[u][i]] >= dep[v]) ans = max(ans, f[u][i]), u = fa[u][i]; if (u == v) return ans; dep(i, 20, 0) if (fa[u][i] != fa[v][i]) ans = max(ans, f[u][i]), ans = max(ans, f[v][i]), u = fa[u][i], v = fa[v][i]; ans = max(ans, f[u][0]); ans = max(ans, f[v][0]); return ans; } ``` ## P4665 [BalticOI 2015] 喵喵构造题。 可以发现连叶子节点最优。然后按照 dfs 序，将 $i$ 和 $i + \frac{n}{2}$ 两个叶子连起来行了。如果 $n$ 是奇数，最后一个叶子随便挂上一个。 ## P2632 Explorer 挖个坑。感觉可以人类智慧。 比如随机旋转，飞快卡过之类的![/cy](https://cdn.luogu.com.cn/upload/pic/62225.png) ## P5505 [JSOI2011] 分特产 容斥喵喵题。考虑让至少 $i$ 个人没有拿到特产的方案数，使用插板法即为 $$\sum \binom{a_k + n - i - 1}{n - i - 1} \times \binom{n}{i}$$ 然后容斥一下就好了。 注意模数是 $10 ^ 9 + 7$ 不是 $998244353$ [流汗黄豆] ```cpp rep(i, 0, n) { int cnt = 1; rep(j, 1, m) cnt = cnt * C(a[j] + n - i - 1, n - i - 1) % mod; ans = ans + ((i & 1 ? -1 : 1) * C(n, i) * cnt % mod); ans %= mod; ans += mod; ans %= mod; } printf("%lld\n", ans); return 0; ``` ## CF160D Edges in MST 比较典的题。求无向图中那些边可能是 / 一定不是 / 一定是最小生成树中的边。 可以先拎出一颗最小生成树，然后枚举非树边 $\left \langle u, v \right \rangle$。如果路径 $(u, v)$ 中的最大值比 $w_{u, v}$ 小，则 $\left \langle u, v \right \rangle$ 一定不在最小生成树中。否则路径 $(u, v)$ 中所有权值等于 $w_{u, v}$ 的点都可能是最小生成树中的边。 考虑标记这些边。一种显而易见的方法是直接上线段树合并。 [$\text{AC code}$](https://www.luogu.com.cn/record/136938123) ## CF1096E The Top Scorer 加训数学。题意大概如下：有 $p$ 个人考试，已知他们的总分为 $s$。现在知道一号选手得分 $\ge r$。求一号选手能够获得第一名的概率。特别的，如果有多个人分数相等且最高，则他们获得第一名的概率相等。 考虑枚举一号选手的成绩 $x \in [r, s]$。然后枚举与一号选手成绩相等的人数 $i$（包括一号选手本身）。剩下选手的总成绩 $s - i \times x$，个数 $p - i$。设 $\text{calc}(n, s, k)$ 表示 $n$ 个选手，总成绩为 $s$，最高成绩 $< k$ 的方案数。则答案为 $\sum \limits_{x = r}^{s} \sum \limits_{i = 1}^{p} \dbinom{p - 1}{i - 1} \times \text{calc}(p - i, s - ix, x)$。 接下来考虑 $\text{calc}$ 怎么搞。首先比较 naive 的是 $n$ 个人总和为 $s$ 且每个人都大于等于 $0$ 的方案数，根据插板法就是 $\dbinom{s + n - 1}{n - 1}$。 那么正难则反，可以直接容斥一下。假设至少 $i$ 个人分数 $\ge k$，容斥系数为 $(-1)^i \dbinom{n}{i}$。方案数是 $\dbinom{n - i \times k + n - 1}{n - 1}$。这个方案数可以理解成，把 $> k$ 的都削掉了 $k$，剩下的就无限制了。 然后注意没有意义的组合数不能计算贡献。时间复杂度 $O(s p ^ 2)$。 ```cpp int calc(int n, int s, int k) { if (n == 0) return s == 0; int ans = 0; rep(i, 0, n) { if (i * k > s) break; int u = s - i * k + n - 1; int v = n - 1, S = C(n, i) * C(u, v) % mod; ans += (i & 1 ? -1 : 1) * S % mod; ans = (ans % mod + mod) % mod; } return ans; } signed main() { read(p, s, r); fac[0] = inv[0] = 1; rep(i, 1, 6000) fac[i] = fac[i - 1] * i % mod; inv[6000] = qpow(fac[6000]); dep(i, 5999, 1) inv[i] = inv[i + 1] * (i + 1) % mod; rep(x, r, s) { rep(i, 1, p) { if (i * x > s) continue; int S = C(p - 1, i - 1) * calc(p - i, s - x * i, x) % mod; ans = ans + S * qpow(i) % mod; ans %= mod; } } int B = C(s - r + p - 1, p - 1); printf("%lld\n", ans * qpow(B) % mod); return 0; } ``` ## CF838D Airplane Arrangements CF2700，好仙的题。不看题解死也想不到。 首先转化成 $n + 1$ 长度的环，每个点随机起点和方向，不能走到 $n + 1$ 号点。 由于这是一个环，每个点没被占据的概率是相同的，即为 $\dfrac{n + 1 - m}{n +1}$。因此答案就是概率乘以总方案数即为 $\dfrac{n + 1 - m}{n +1} \times (2 ^ m (n + 1) ^ m)$。再解释一下，$2 ^ m$ 表示方向，$(n + 1) ^ m$ 表示第 $i$ 个人初始点的位置。 ```cpp int p = (n - m + 1) * qpow(n + 1) % mod; int b = qpow(2, m) * qpow(n + 1, m) % mod; write('\n', p * b % mod); return 0; ``` ## CF997C 推了个式子出来好像错了。但是是线性的。先搁这放着。 设至少 $i$ 行 $j$ 列染成了相同颜色。然后考虑容斥。 - $i$ 为 $0$。那么方案数为 $$\sum_{i = 1}^{n} (-1) ^ {i} \dbinom{n}{i} 3 ^ i 3 ^ {n(n - i)}$$ - $j$ 为 $0$，其方案数与 $i = 0$ 相同。 - $i, j$ 均不为 $0$。方案数为： $$\sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j + 1} \dbinom{n}{i} \dbinom{n}{j} 3 \times 3 ^{(n - i)(n - j)}$$ 然后发现这个大组合可以拆成两半，而且两半还对称。所以就 $O(n)$ 了。 然鹅似乎并不对。不管了。 $\text{update on 2023-12-03:}

找到锅了。x^{ab} = (x^a)^b 而不是 x^a x^b。wssb。

第二个式子可以化成：

(-3) \times \sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j} \dbinom{n}{i} \dbinom{n}{j} 3 ^{(n - i)(n - j)}

考虑右边的一大坨：

\sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j} \dbinom{n}{i} \dbinom{n}{j} 3 ^{(n - i)(n - j)} = \sum_{i = 1}^{n} (-1)^i \dbinom{n}{i} \sum_{j = 1}^{n} (-1)^j \dbinom{n}{j} 3 ^{(n - i)(n - j)}

设 w = 3 ^ {n - i}。原式变成：

\sum_{i = 1}^{n} (-1)^i \dbinom{n}{i} \sum_{j = 1}^{n} \dbinom{n}{j} (-1)^j w^{n - j}

抠出右边的式子，二项式定理逆用一下可以发现：

\sum_{j = 1}^{n} \dbinom{n}{j} (-1)^jw^{n - j} = (w - 1)^n - w^n

所以原式就是：

\sum_{i = 1}^{n} (-1)^i \dbinom{n}{i} \left ( (w- 1)^n - w ^ n \right )

复杂度 O(n \log n)，瓶颈在快速幂。

真的，这道题让我对组合数学的理解加深了很多。

signed main() {
    // init combinations
    read(n); fac[0] = inv[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod; inv[n] = qpow(fac[n]);
    dep(i, n - 1, 1) inv[i] = inv[i + 1] * (i + 1) % mod;
    // the first part
    rep(i, 1, n) {
        int s = qpow(3, i + n * (n - i)) * C(n, i) % mod;
        ans += (i & 1 ? 1 : -1) * s; ans = (ans % mod + mod) % mod;
    } ans = ans * 2; 
    // the second part
    int res = 0;
    rep(i, 1, n) {
        int w = qpow(3, n - i);
        int b = qpow((w - 1 + mod) % mod, n);
        b = b - qpow(w, n); b = (b + mod) % mod;
        int s = C(n, i) * b % mod;
        res += (i & 1 ? -1 : 1) * s;
        res = (res % mod + mod) % mod;
    } res = res * (-3) % mod;
    res = (res + mod) % mod;
    write('\n', (ans + res) % mod);
}

CF1097D Makoto and a Blackboard

题意：给定正整数 n 和 k 次操作，每次操作把 n 等概率变为其约数。求最终 n 的期望。

喵喵题，还没写，但是做法能胡一下。

首先考虑将 n 拆成质因数分解形式 n = \prod_{i = 1}^{m} p_i ^{c_i}。发现对于每个质因子答案相对独立。所以可以对每个质因子单独求答案。

设 f_{i, j} 表示操作了 i 次质因子 p 的次数变为 j 的概率的期望。转移显然是：

f_{i, j} = \sum_{k = j}^{c} \dfrac{1}{k + 1} f_{i - 1, k}

复杂度 k \log n 完成转移。然后对于 p 这个质因子的答案 g_p = \sum f_{k, i} \times p^i。

最后合并答案，这个东西显然是积性函数，所以答案就是 ans = \prod g_{p_i}。

bonus：虽然对于每个质数求 f 是 O(\log n) 的，n 的质因子个数也是 O(\log n) 级别的，看起来似乎是 \log ^ 3 n 状物，但是复杂度却是严格小于双 \log 的。

神鱼写了看不懂的东西。当然我并不会。 头一次十分钟之内写完 CF2000+ 的题。贴一下 $k \le 10 ^ 4$ 的朴素实现。 ```cpp int calc(int p, int c) { rep(i, 0, c) f[0][i] = f[1][i] = 0; f[0][c] = 1; rep(i, 1, k) rep(j, 0, c) { f[i & 1][j] = 0; rep(w, j, c) f[i & 1][j] += f[(i & 1) ^ 1][w] * qpow(w + 1) % mod, f[i & 1][j] %= mod; } int s = 0; rep(i, 0, c) s = (s + qpow(p, i) * f[k & 1][i] % mod) % mod; return s; } signed main() { read(n, k); rep(i, 2, n / i) if (n % i == 0) { int cnt = 0; while (n % i == 0) cnt ++ , n /= i; ans = ans * calc(i, cnt) % mod; } if (n != 1) ans = ans * calc(n, 1) % mod; write('\n', ans); return 0; } ``` ## CF1264D1 Beautiful Bracket Sequence (easy version) 可以发现最后任何合法的括号序列都可以删成形如 $\texttt{(((...)))}$ 的形式而最大深度不变（也即每个合法括号序列要想变成最大深度，一定要删成一段 $\texttt{(}$ 拼上一段 $\texttt{)}$ 的形式）。 因此可以 dp。设 $f_{i, j}$ 表示前 $i$ 个字符有 $j$ 个左括号的方案数，$g_{i, j}$ 表示 $i \sim n$ 有 $j$ 个 $)$ 的方案数。$O(n ^ 2)$ 转移即可。 ```cpp f[0][0] = 1; rep(i, 1, n) rep(j, 0, i) { if (s[i] == '(') (f[i][j] += f[i - 1][j - 1]) %= mod; if (s[i] == ')') (f[i][j] += f[i - 1][j]) %= mod; if (s[i] == '?') (f[i][j] += (j ? f[i - 1][j - 1] : 0) + f[i - 1][j]) %= mod; } g[n + 1][0] = 1; dep(i, n, 1) rep(j, 0, n) { if (s[i] == ')') (g[i][j] += (j ? g[i + 1][j - 1] : 0)) %= mod; if (s[i] == '(') (g[i][j] += g[i + 1][j]) %= mod; if (s[i] == '?') (g[i][j] += (j ? g[i + 1][j - 1] : 0) + g[i + 1][j]) %= mod; } rop(i, 1, n) rep(j, 1, n) (ans += f[i][j] * g[i + 1][j] % mod * j % mod) %= mod; ``` bonus：本题的组合做法： 枚举最终左右括号的分界位置。设 $[1, i]$ 中有 $s_1$ 个 $\texttt{(}$，$s_2$ 个 $\texttt{?}$；$[i + 1, n]$ 中有 $s_3$ 个 $\texttt{)}$，$s_4$ 个 $\texttt{?}$。那么对于这个分界点，方案数就是： $$\sum_j \dbinom{s2}{j - s1} \dbinom{s4}{j - s3} j$$ 其中 $j$ 表示枚举的左右括号的数量，$s_1, s_2, s_3$ 可以前缀和。时间复杂度 $O(n ^ 2)$。 ```cpp rep(i, 1, n) s1[i] = s1[i - 1] + (s[i] == '('); dep(i, n, 1) s2[i] = s2[i + 1] + (s[i] == ')'); rep(i, 1, n) s3[i] = s3[i - 1] + (s[i] == '?'); rep(i, 1, n) fac[i] = fac[i - 1] * i % mod; inv[n] = qpow(fac[n]); dep(i, n - 1, 1) inv[i] = inv[i + 1] * (i + 1) % mod; rep(i, 1, n) rep(j, 1, n) { int S1 = s1[i], S2 = s3[i]; int S3 = s2[i + 1], S4 = s3[n] - s3[i]; ans += C(S2, j - S1) * C(S4, j - S3) % mod * j; ans %= mod; } write('\n', ans); return 0; ``` ## CF1264D2 Beautiful Bracket Sequence (hard version) 上一道题的加强版，也是第一道自己做出来的黑 / CF2900。 把上面一个题的组合式子变形一下即可。 ```cpp rep(i, 1, n) { int S1 = s1[i], S2 = s3[i]; int S3 = s2[i + 1], S4 = s3[n] - s3[i]; ans += S1 * C(S2 + S4, S4 + S3 - S1) % mod; ans %= mod; ans += S2 * C(S2 + S4 - 1, S4 + S3 - S1 - 1) % mod; ans %= mod; } write('\n', ans); return 0; ``` 变形方法下午写。 $\text{update}$： 原式为： $$sum = \sum_j \dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3} j$$ 我们把 $j$ 拆成 $(j - s_1) + s_1$。那么原式变成： $$sum = \sum_j \dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3} (s_1 + (j - s_1))$$ $$= \sum_j s_1\dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3} + \sum_j (j - s_1)\dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3}$$ $$= s_1 \sum_j \dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3} + \sum_j (j - s_1)\dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3}$$ 接下来用到一个组合恒等式： > $$\binom{m}{k} \binom{n}{r - k} = \binom{m + n}{r}(r = \min(n, m))$$ 因此前面一半式子就是： $$s_1 \sum_j \dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3}$$ $$= s_1 \sum_j \dbinom{s_2}{j - s_1} \dbinom{s_4}{s_4 - j + s_3}$$ $$= s_1 \binom{s_2 + s_4}{s_3 + s_4 - s_1}$$ 后面一半式子需要用到另外一个组合恒等式： > $$\binom{n}{k} = \dfrac{n}{k} \binom{n - 1}{k - 1}$$ 因此可以把第二个式子中的 $j$ 约掉，得到： $$\sum_j (j - s_1)\dbinom{s_2}{j - s_1} \dbinom{s_4}{j - s_3}$$ $$= \sum_j s_2 \dbinom{s_2 - 1}{j - s_1 - 1} \dbinom{s_4}{j - s_3}$$ $$= s_2 \sum_j \binom{s_2 + s_4 - 1}{s_3 + s_4 - s_1 - 1}$$ 将两部分加起来就是答案。时间复杂度 $O(n)$。 ## [ARC093F] Dark Horse 好难。不看题解想不到一点。 首先转化题目：将序列分成长度为 $1, 2, 4 \cdots 2 ^ {n - 1}$ 次方的 $n$ 组，每组内的最小值都不属于 $A$。 然后显然可以容斥。设状态 $s$ 表示当前分组方案中，$s$ 为 $1$ 的这些最小值属于 $A$。总方案就是 $(2 ^ n)! - \sum_s (-1)^{|s|} f(s)$。 然后就是不看题解死也想不到的 dp。 首先把 $A$ 从大到小排序。 设 $g_{i, j}$ 表示当前扫到了 $A$ 的第 $i$ 位，当前分组中，已经分满并且最小值属于 $A$ 的方案数。 转移比较平凡。考虑将 $A_i$ 分进已经填满的组还是没有填满的组。 - 分进填满的组，则有 $g_{i, j} = g_{i - 1, j}$。 - 分进未填满的组，则有 $g_{i, j | 2 ^ k} \leftarrow g_{i - 1, j} \times \dbinom{2 ^ n - j - A_i}{2 ^ k - 1} \times (2 ^ k)!$。 最后，$f(S) = g_{m, S} \times (2 ^ n - S - 1) !$。 又一次被 dp 虐暴了。 ```cpp int F(int s) { return f[m][s] * fac[tot - s - 1] % mod; } int count(int n, int s = 0) { while (n) s += (n & 1), n >>= 1; return s; } signed main() { read(n, m); tot = 1 << n; fac[0] = inv[0] = 1; int lim = N - 5; rep(i, 1, lim) fac[i] = fac[i - 1] * i % mod; inv[lim] = qpow(fac[lim]); dep(i, lim - 1, 1) inv[i] = inv[i + 1] * (i + 1) % mod; rep(i, 1, m) read(a[i]); sort(a + 1, a + m + 1, greater<int>()); f[0][0] = 1; rep(i, 1, m) rop(j, 0, tot) { (f[i][j] += f[i - 1][j]) %= mod; rop(k, 0, n) { if ((j >> k) & 1) continue; f[i][j | (1 << k)] += f[i - 1][j] * C(tot - j - a[i], (1 << k) - 1) % mod * fac[1 << k] % mod; f[i][j | (1 << k)] %= mod; } } rop(s, 0, tot) { ans += (count(s) & 1 ? -1 : 1) * F(s) % mod; ans = (ans % mod + mod) % mod; } ans = ans * tot % mod; write('\n', ans); return 0; } ``` ## CF1536F 可以发现，无论怎么走都是后手必胜。 所以就不用考虑策略了。直接求不同走法的合法方案数即可。 可以发现，不可能有相邻的两个空格。因为如果有相邻的两个空格，只有可能是下面的情况： $\texttt{A\_\_B} \texttt{A\_\_A} \texttt{B\_\_A} \texttt{B\_\_B}

这时候走子方一定能落子。

另外一个性质是，最后的局面除掉格子外一定是 \texttt{ABABABAB} 或者是 \texttt{BABABABA} 这样的格式。

因此考虑枚举当前进行了 2i 步，剩下了 n - 2i 个空格子。由于这是个环，所以分第一个是不是空格来计算。

假设第一个是空格，那么最后一个肯定不是空格。相当于在 2i + 1 - 2 个空（减掉的二是首位两个）里面插入 2i - 1 个板（减掉的一个板子是开头的板）。方案数就是 \dbinom{2i - 1}{n - 2i - 1}。

假设第一个不是空格，那么方案数就是 \dbinom{2i}{n - 2i}。

因此总方案数就是

2 \times \sum_{i = 1}^{\frac{n}{2}} (2i)! \left ( \dbinom{2i - 1}{n - 2i - 1} + \dbinom{2i}{n - 2i} \right )

时间 O(n)。不知道为什么标签写了个中国剩余定理。

rep(i, 1, n >> 1) {
    int s = C(2 * i, n - 2 * i) + C(2 * i - 1, n - 2 * i - 1);
    ans = (ans + fac[2 * i] * s % mod) % mod;
} ans = 2 * ans % mod; write('\n', ans);

CF906D

一眼奶了。这不就欧拉降幂板子。

乍一看每次询问都得 O(n)。但是再想想，\varphi(\varphi(\cdots \varphi(n))) 的下降速度是非常快的，\log 次就降成 1 了。所以直接暴力递归就可以了。时间复杂度显然 O(m \log p)。

这就是 CF2700？

\text{AC code}