做题记录 25.3.27

szt100309 · 2025-03-27 08:13:34 · 个人记录

比赛

\textcolor{black}\odot P4931 [MtOI2018] 情侣？给我烧了！（加强版）

令 f_i 表示 i 对都不合法的方案数，则 (n,k) 的答案为 C_n^kA_n^k2^k f(n-k)，问题转化为如何求出 f

其通项公式为 f_k=\sum_i (-1)^i (2k-2i)!C_k^i A_k^i 2^i，可以卷积，但可以做到线性

显然 f_0=1，已知 f_{0\sim i}，考虑如何递推到 i+1

第 i+1 行必须坐不匹配的，共 2i(2i+2) 种选法

设第 i+1 行两个另一半坐在一起，显然也不匹配，贡献为 2if_{i-1}

若不坐在一起，则将两者看做一对相匹配的，贡献为 f_i

因此 f_{i+1}=4i(i+1)f_i+8i^2(i+1)f_{i-1}

时间复杂度 O(V+T)

代码

参考

\textcolor{black}\odot CF1085G Beautiful Matrix

即计算字典序小于给定矩阵的合法矩阵 A' 数量

枚举第一个不同的位置 (i,j)，需要计算 A'(1\sim i-1,1\sim n)=A(1\sim i-1,1\sim n),A'(i,1\sim j-1)=A(i,1\sim j-1),A'(i,j)<A(i,j) 的合法 A' 数量

令 d_{i,j} 表示 i 个元素放置到 i 个位置，其中对于 1\le x\le j，第 x 个不能放到位置 x 的方案数（计算过程在后面）

显然 d_{i,i} 为错排数列

当 i>1 时，显然 A'(i,j\sim n) 为 A(i,j\sim n) 的一个排列，且 \forall j\le x\le n,A'(i,x)\ne A(i-1,x)，A'(i,j)<A(i,j)

显然满足上述条件的一定合法

令 ct=|\{A(i,x)\mid j\le x\le n,A(i,x)<A(i,j),A(i,x)\ne A(i-1,j)\}| 为 A'(i,j) 的方案数

令 p=|\{A(i,x)\mid j\le x\le n\}\cap\{A(i-1,x)\mid j+1\le x\le n\}| 为 A'(i,j+1\sim n) 中可能出现 A'(i,x)=A(i-1,x) 的数量

令 ctl=|\{A(i-1,x)\mid j+1\le x\le n\}\cap \{A(i,x)\mid j\le x\le n,A(i,x)<A(i,j)\}| 为出现 A'(i,j)=A(i-1,j) 的方案数

代码

参考

\purple\odot CF512D Fox And Travelling

每次将选择的点删去，发现每次只能删去叶子或孤点

因此环上的点一定无法被删去，通过拓扑排序求出能删去的点，显然构成森林

一部分为无根树（其所在连通块内没有环），一部分为有根树（所在连通块的一部分）

显然每棵树可以分别计算，最终 r_{i+j}\gets \binom{i+j}{i,j}a_ib_j 合并起来即可

对于有根树，直接 dp 即可，令 dp_{u,c} 表示子树 u 内选择 c 个点的方案数，将所有儿子的 dp 合并起来后令 dp_{u,sz_u}\gets dp_{u,sz_u-1} 即可（所有子树都选后才能选 u）

对于无根树，每个点都做一次上述操作，将答案加起来，令 t_i 表示选择 i 个的累计答案，则选择 i 个的实际答案为 \frac{t_i}{sz-i}，其中 sz 为无根树大小（假定 0^{-1}=1）

总时间复杂度 O(n^3)，存在 O(n^2) 算法

代码

参考

\purple\odot P4128 [SHOI2006] 有色图

设点的置换为 p，p 的各个循环长度为 a_{1\sim k}，其中 a 单调不降

暴力搜索枚举所有 a_{1\sim k}\;((\forall 1\le i<k,a_i\ge a_{i+1}),(\forall 1\le i\le k,a_i\in\mathbb N^*),\sum_{i=1}^k a_i=n)（一共不超过 10^6 种）

对于给定的 a_{1\sim k}，对应的置换数量为 \dfrac{n!}{\prod a_i\prod cnt_x!}，其中 cnt_x=\sum [a_i=x]

根据 \text{P\'olya} 计数，总方案数为 \frac{1}{|G|}\sum_{p\in G} m^{C(p)}，当前的一组 a_{1\sim k} 对应 G 中 \dfrac{n!}{\prod a_i\prod cnt_x!} 个元素，所有元素的 C(p) 相同，因此转化为求当前的 a 对应的 C(p)（点置换下边的循环数量）

对于两端不在同一循环中的边，设两端分别在 a_i 和 a_j 对应的循环中（1\le i<j\le k），则这组 (a_i,a_j) 对应的循环长度为 \operatorname{lcm}(a_i,a_j)，数量为 \dfrac{a_ia_j}{\operatorname{lcm}(a_i,a_j)}=\gcd(a_i,a_j)

对于两端在同一循环中的边，设在 a_i 对应循环中，则 a_i 为奇数时数量为 \frac{\binom{a_i}2}{a_i}=\frac{a_i-1}2，为偶数时循环节长为 \frac{a_i}2 的单独计算，数量为 \frac{\binom{a_i}2-\frac{a_i}2}{a_i}+1=\frac{a_i}2，综上数量为 \lfloor\frac{a_i}2\rfloor

因此一组 a_{1\sim k} 的总贡献为

总时间复杂度 O(p(n))，其中 p(n) 为 n 的拆分数

代码

参考 1

参考 2

来自璃月的生日礼物

转化为 (1,0) 到 (m,n-m) 的两条不降路径，两者不互相穿越，求方案数

将上方非一条向左上平移，转化为 (0,1)-(m-1,n-m+1) 和 (1,0)-(m,n-m) 的两条不交路径的方案数

使用 \text{LGV} 引理即可

时间复杂度 O(n)

可优化至 O(\sqrt n\log n)

代码

\textcolor{black}\odot CF708E Student's Camp

常规 dp 为令 dp_{i,l,r} 表示第 i 行的区间为 [l,r] 的方案数，发现状态数无法接受

对于每种可能的最终情况，从第 0 行出发，能向下则向下，否则向左右移动，直到第 n+1 行，显然一个状态对应的路径唯一

令 lm_{i,j},nm_{i,j},rm_{i,j} 表示从第 i-1 行到第 i 行时位置在 (i,j)，且在第 i-1 行中从左向右走 / 不动 / 从右向左走，第 1\sim i-1 行的状态的概率

令 a_{i}=\binom ki p^i (1-p)^{k-i} 表示一行中消去长为 i 的前 / 后缀的概率，s_i 为 a 的前缀和

则 lm_{1,i}=1，转移为

答案为 \sum_{i=1}^m lm_{n,i}a_{i-1}s_{m-i}+nm_{n,i}s_{i-1}s_{m-i}+rm_{n,i}s_{i-1}a_{m-i}

前缀和优化可做到 O(nm)

代码

参考

QOJ # 9254. Random Variables

枚举 1\le k\le n 计算众数出现次数 \le k 的数量，设结果为 r_k 则答案为 (n+1)m^n-\sum_{i=1}^n r_i

考虑如何计算一个 r_k

令 dp_{i,j} 表示放置了 i 个数，其中 j 种数字出现次数可以超过 k 的方案数，则 r_k=dp_{n,0}，边界为 dp_{0,\ast}=1

考虑 dp_{i,j} 的转移，显然第 i 个数有 m-j 种选择，转移为 dp_{i,j}\gets (m-j)dp_{i-1,j}（即没有新增的可以超过 k 的数字）

当 i>k 时，需要减去出现超过 k+1 次的情况，dp_{i,j}\gets -(m-j){dp}_{i-k-1,j+1}\binom{i-1}k（即减去位置 i 与前面 k 个位置值相同的情况）

显然 j\le\frac n{k+1}，因此单次时间复杂度为 O(n\frac nk)

总时间复杂度 O(\sum n^2\ln n)

代码

参考