12.7 计划

· · 个人记录

2022.12.7 - 2023.1.13

（题目待整理）

P1 图论 & 树论

blog1||blog2||blog3

P2 数据结构

P8576 「DTOI-2」星之界

题目传送门

操作一显然用并查集维护值，接下来考虑对操作二进行化简：

\displaystyle \prod_{i=l}^r \binom{\sum_{j=l}^ia_j}{a_i}

设 f(i)=\displaystyle\binom{\sum_{j=l}^ia_j}{a_i}，显然：

f(l)=1=\displaystyle\frac{(a_l)!}{(a_l)!} f(l+1)=\displaystyle\binom{a_l+a_{l+1}}{a_{l+1}}=\frac{(a_l+a_{l+1})!}{(a_l)!(a_{l+1})!} f(l+2)=\displaystyle\binom{a_l+a_{l+1}+a_{l+2}}{a_{l+2}}=\frac{(a_l+a_{l+1}+a_{l+2})!}{(a_l+a_{l+1})!(a_{l+2})!} \displaystyle\prod_{i=l}^r f(i)=\frac{(a_l+a_{l+1}+...+a_r)!}{(a_l)!(a_{l-1})!...(a_r)!}

所以对于每一个整块，需要维护的值是：

显然用并查集记录 size，乘积用乘法逆元更新即可。例如 k 个 x 转为 y，那么和变化为 x.size\times (y-x)，乘积变化为 (y!)^{x.size}\times \big(inv(x!)\big)^{x.size}。

修改散块直接暴力重构就可以了。

询问时暴力询问散块阶乘乘积和和值，整块访问 tag 就可以了。

由于并查集一次修改时间复杂度为 O(\alpha(n))，值域与 n 同阶，每块修改次数不会超过 n 次，所以时间复杂度为 O(n\sqrt n)。

record

题单1||题单2

P3 计数专项

题单

P5363 [SDOI2019]移动金币

题目传送门

首先转化题意，可以发现由于最终状态为 m 个金币都在左侧，所以任意两个金币之间的间隔都为 0，而移动一次第 i 枚金币会使 i 至 i-1 的间隔减 1，i 至 i+1 的间隔加 1。

所以可以将金币至前一枚金币的间隔抽象为一堆石子（第一堆就是第一枚硬币离第 0 格的距离），这时可以发现操作变为：每次可以选择一个石子，将其扔到下一堆，最后一堆扔出的石子则直接丢弃。

这就是一个典型的阶梯 nim 游戏了，而这个游戏的经典结论就是：必败局面当且仅当奇数位置石堆石子个数的异或和为 0。

由于必败的特殊性质使得统计方便，所以使用容斥：设必败局面有 t 种，而从 n 个格子中选出 m 个格子放金币的方案总数为 \binom{n}{m}，所以最后答案就是 \binom{n}{m}-t。

接下来的问题就转化为：求石子总数不超过 n-m，石堆个数为 m 的阶梯 nim 游戏的必败情况总数，由于这个阶梯 nim 的丢弃点在右边，所以需要满足的条件是偶数堆异或和为 0。

于是可以看出，由于右边还会有一段空间，所以奇数堆的总数为 x=\lfloor\frac{m+2}{2}\rfloor ，偶数堆总数为 y=\lfloor\frac{m+1}{2}\rfloor。

观察到异或和为 0 的重要条件：每一个二进制位上出现的 1 的个数必须为偶数，所以可以通过 dp 求解，用 dp_{i,j} 表示处理完第 i 个二进制位，已使用石子数为 j 时的方案总数，显然有以下转移：

dp_{i,j}=\displaystyle \sum_{k=0}^{y} dp_{i-1,j-k \times 2^i}\times \binom{y}{k} \cdot [k \% 2==0]

边界条件 \displaystyle dp_{0,2i}=\binom{y}{2i}(0 \leq 2i \leq y)。

用插板法求解，在统计答案 dp_{lim,i} 时会将 n-i 个石子放到 x 个堆里，所以需要乘上 \displaystyle\binom{x-1+n-i}{x-1}。

[record](https://www.luogu.com.cn/record/97252216) ## P2490 [SDOI2011]黑白棋 [题目传送门](https://www.luogu.com.cn/problem/P2490) 显而易见的一点是，每一个白棋和后一个黑棋是单独匹配的，它们不可能影响到其余的棋子。 所以题目转化为 $nim$ 游戏计数：而有所不同的就是可以在选择不超过 $d$ 个石堆中拿取若干个石子，就是一个 $k-nim$ 游戏。 > k-nim 游戏结论：先手必败当且仅当所有二进制位上的和 $cnt \% (k+1)$ 的结果都为零 所以接下来可以通过枚举各个二进制位上的个数来转移 $dp$，同样的，用 $dp_{i,j}$ 表示已完成第 $i$ 位选择，使用了 $j$ 颗石子的方案数。 转移方程式同上，直接枚举每一位填上 $l(d+1)$ 个格子。显然上界为 $m/2$。 边界条件 $dp_{0,i(d+1)}=\displaystyle \binom{m/2}{i(d+1)}

在统计答案 dp_{lim,i} 时会将 n-i 个石子放到 m+1 个堆里，所以需要乘上 \displaystyle\binom{m+n-i}{m}。

时间复杂度 O(nm \log n)

record

[AGC025B] RGB Coloring

题目传送门

可以发现，给一个格子涂上绿色相当于同时涂上蓝色和红色，这时涂色方案就相互独立了（随意涂色完成后将重复涂色位置看做绿色即可）。

通过枚举解方程 Ax+By=K，对于满足条件的 x,y，贡献显然为 \displaystyle \binom{n}{x}\times \binom{n}{y}

然后加起来就可以了。

时间复杂度 \Theta(n)。

record

P2051 [AHOI2009] 中国象棋

题目传送门

由于每一行有放 0,1,2 个三种决策，并且每一列不能超过两个，所以设计 dp 状态 dp_{i,j,k} 表示处理到第 i 行，有 j 列没有放棋子，k 列放了一颗棋子，显然有 m-j-k 列为 2 颗棋子（需要保证状态合法），所以设 t=m-j-k，那么会有以下状态转移：

不放棋子：

dp[i+1][j][k]+=dp[i][j][k]

放一颗：

dp[i+1][j-1][k+1]+=dp[i][j][k] \times j dp[i+1][j][k-1]+=dp[i][j][k]\times k

放两颗：

dp[i+1][j-1][k]+=dp[i][j][k] \times j \times k dp[i+1][j-2][k+2]+=dp[i][j][k] \times j \times (j-1) /2 dp[i+1][j][k-2]+=dp[i][j][k] \times k \times (k-1) /2

边界条件为 dp[0][m][0]=1

最后答案显然是 \sum dp[n][i][j] (i+j \leq n)

时间复杂度 O(nm^2)。

record

P2150 [NOI2015] 寿司晚宴

半年前做过的题了，今天重写/描述一遍来回顾状压 dp 和根号分治的思路。

大致题意：求从 2 ~ n 中选定若干个数组成两个互斥集合，并使得两个集合间不存在公共质因数的方案总数。(2\leq n \leq 500)

先看部分分 n \leq 30，发现小于 30 的质数只有 10 个，优先处理出每个数的质因数，然后使用二进制状压的方式保存，因此可以使用状压 dp 处理，状态转移方程：

dp[i][j|a[i]][k]+=dp[i-1][j][k] dp[i][j][k|a[i]]+=dp[i-1][j][k] dp[i][j]+=dp[i-1][j][k]

合法状态自然是 j\&k=0

时间复杂度 \Theta(n\times 4^{10})。

考虑到每个数至多有一个大于等于 \sqrt n 的质因数，所以可以处理出每个数大于 \lfloor\sqrt{500}\rfloor = 22 的质因数。这时所含有的小于 \sqrt n 的质因数集合为 \{2,3,5,7,11,13,17,19\}，共 8 个。

在预处理出大质因数之后按“大质因数”排序，可以使“大质因数”相同的数并在一起，而这一个连续区间的取值只有两种可能：

使用两个数组分别递推即可。时间复杂度 \Theta(n\times 4^8)。

细节不小，暂时不写。

P2106 Sam数

题目传送门

先考虑 \Theta(n) 的常规 dp，以最后一位作为状态，那么有 dp_{i,j}=\sum dp_{i-1,k}[|j-k| \leq 2]

所以可以构造矩阵描述递推 [dp_0,dp_1,dp_2,...,dp_9]。

具体就是在满足 |i-j|\leq 2 的位置都填上 1，其他位置填 0 ，初始数组 dp_0=0，其他为 1。

时间复杂度 \Theta(\log n)，不过有一个 11^3 的常数。

评价：恶评矩阵加速板子，蓝顶天了。

record

P6669 [清华集训2016] 组合数问题

record

注：以下相等有相当一部分是模 k 意义下的。

由于 n,m 很大并且 k 很小，显然可以利用 Lucas 定理：\displaystyle\binom{n}{m}=\binom{n\%k}{m\%k} \times \binom{n/k}{m/k} 可以分析出：\displaystyle\binom{n}{m}=\prod_{a=n,b=m}^{a=a/k,b=b/k,a,b \geq 0}\binom{a\%k}{b\%k}，显然，当 a\%k < b\%k 时，其中一项为 0，结果也就是 0。

所以现在的问题就是，在 k 进制下满足某位上数字大于 i 的 j 的个数，显然使用数位 dp。

用记忆化搜索实现，由于不需要处理前导 0，所以选择状态 dp_{pos,pre,lim1,lim2,bi} 表示 dp 到了第 pos 位某一位上的 j>i 的条件是否实现，i 是否受到上限影响，i 是否受到上限影响。前面位数中 i 是否等于 j。

record

P4 构造专项

题单

P5 杂类题目

P3936 Coloring【模拟退火】

题目传送门

首先发现题目要求的 q 就是不同颜色的色块之间的边的个数。

所以优先构造一个序列，然后用模拟退火的方式 swap 两个序列。

发现折返式构造可以得 70pts。。。

由于 rp 不够，交了 84 次之后满分了。

record