dp 专场 *2。
CF1608F MEX Counting
题意：给出 \(n,m,b_{1...n}\)，求出有多少个长度为 \(n\) 的序列 \(a\) 满足 \(\forall i\in[1,n],\space 0\le a_i\le n\) 且 \(|\operatorname{mex} \{a_1,a_2,...,a_i\}-b_i|\le m\)。
\(1\le n\le 2000,\space 1\le k\le 50\)
很简单的 dp，个人认为难度下位紫或更低（？）
考虑枚举 \(i=1,2,...,n\)，依次填写 \(a_1,a_2,...,a_n\)，并维护当前的 \(\operatorname{mex}\) 结果，不妨设为 \(j\)。当前填的数有三种：
-
\(<j\)，并不会产生什么影响
-
\(=j\)，此时当前的 \(\operatorname{mex}\) 会变大，变大多少取决于 \(j\) 后面一段已填过的数的个数。
-
\(>j\)，这个数字可能对未来有影响，但我们目前未知
直接 dp，设 \(f[i,j,k]\) 表示填完前 \(i\) 个数，并且 \(\operatorname{mex}\) 结果为 \(j\)，其中还有 \(k\) 种数 \(>j\)。
考虑 \(a_i\) 的影响，如果 \(\operatorname{mex}\{a_1,a_2,...,a_{i-1}\}\) 还是 \(j\)，那么 \(a_i<j\) 或 \(a_i>j\)，转移：
-
如果 \(>j\) 的数字种类数不变：\(f[i,j,k]\gets f[i-1,j,k]\times(j+k)\)
-
如果 \(>j\) 多了一个数字种类：\(f[i,j,k]\gets f[i-1,j,k-1]\times k\)
注意我们不计算这 \(k\) 种数的取值贡献，而是他们之间的相对大小顺序。
接下来如果 \(\operatorname{mex}\{a_1,a_2,...,a_{i-1}\}<j\)，不妨设为 \(x\)，那么中间 \([x+1,j-1]\) 这一段一定都在前 \(i-1\) 个数出现过，我们不妨直接拿其中 \(>x\) 中的一些填入这 \((j-1)-(x+1)+1=j-x-1\) 个数中。由于我们已经考虑了相对大小顺序，直接拿最小的那几个填入即可。
- 转移： \(f[i,j,k] \gets f[i-1,x,k+(j-x-1)]\)
总转移式
\[f[i,j,k]=f[i-1,j,k]\times (j+k)+f[i-1,j,k-1]\times k+\sum_x f[i-1,x,k+j-x-1] \]\(j\) 个数为 \(O(m)\)，前缀和优化即可做到 \(O(n^2m)\)。
实现时注意细节问题。 记录
CF1450G
题意：一个小写字母组成的字符串 \(s\)，其中字母 't', 'r', 'y', 'g', 'u', 'b' 不会出现，还给定了一个有理数 \(k=\frac ab\)。
每次可以选择 \(s\) 中的一种字母，将 \(s\) 中所有的这种字母变成另一种字母，但有个条件：设这个字母出现了 \(c\) 次，需要覆盖这 \(c\) 个位置的最小区间为 \([l,r]\)，那么需要满足 \(k\cdot (r-l+1)\le c\)。
对于所有 \(s\) 中出现的字母，求出是否可以通过若干次操作使得 \(s\) 中全是这种字母。
\(1\le n\le 5000,\space 1\le a\le b\le 10^5\)
因为有 \(6\) 种字母不会出现，所以一共只有 \(20\) 种，可以考虑状压。
我们把字母分类，一类是一开始就不合法的，另一类是一开始合法的。
一开始已经合法的两种字母显然不需要合并，因此我们一开始需要将一种合法的字母合并到一种不合法的，然后产生一个新的状态。
如果还不合法则继续合并，直到这个字母合法，此时这是一个字母集合（合并的集合），然后把他作为一个新的合法“字母”继续合并。
设 \(f[S]\) 表示是否可以把 \(S\) 中的字母合并起来，并且合并出去。
-
把 \(S\) 中的字母分成两个合法集合，显然这两个集合可以分别合并出去，不需要额外合并起来：\(f[S\cup T]\gets f[S]\operatorname{and} f[T]\)
-
合并到一个本来不合法的字母：\(f[S\cup \{x\}]\gets f[S]\)
时间 \(O(3^n)\)，需要优化。
注意到如果两个集合 \(S_1,S_2(S_1\cap S_2=\emptyset)\) 对应的覆盖区间有交，且 \(S_1,S_2\) 都是合法的，那么 \(S_1\cup S_2\) 一定是合法的。
观察这能给我们什么思考，我们在第一种转移中枚举 \(T\)，如果 \(S\) 和 \(T\) 对应的覆盖区间有交且 \(f[S]=f[T]=1\)，那么一定得到 \(f[S \cup T]=1\)。
进一步的，钦定 \(S\) 和 \(T\) 都是由若干个合法的集合合并到一个不合法的字母形成的，设这两个字母为 \(x,y\)，设 \(S'=S\oplus \{x\}\)，其实我们可以先把 \(T\) 与 \(S'\) 合并，再转为 \(x\)。由于 \(S,S',T\) 都合法，如果去掉 \(x\) 后 \(S',T\) 对应区间仍然有交，则 \(f[S'\cup T]=1\)；如果无交，通过第一种转移也可以使得 \(f[S'\cup T]=1\)。
对于 \(S,T\) 由多个集合合并起来的，可知每个集合都合法。拆分每个集合，如果可以找到一条分界线来分划这些集合对应区间显然合法；如果找不到，依次合并起来就好。
因此，第一种转移时，我们枚举的 \(S,T\) 额外保证 \(S,T\) 对应区间无交，即可优化。设 \(k\) 为字母种类数，时间 \(O(k2^k)\)。 记录
CF1621G Weighted Increasing Subsequences
题意：给出 \(n,a_{1...n}\)，对于每个上升子序列 \(a_{i_1},a_{i_2},...,a_{i_m}\)，子序列中 \(a_{i_j}\) 有贡献当且仅当存在 \(k\) 满足 \(k>i_m\) 且 \(a_{i_j}<a_k\)，求所有上升子序列的贡献和，模 \(10^9+7\)。 \(1\le n\le 2\times 10^5,\space 1\le a_i\le 10^9\)
考虑把 \(a\) 转化为一个排列 \(p\)，相同的数则前面比后面大。不妨考虑 \(q=p^{-1}\)，\(p\) 的上升子序列仍然对应 \(q\) 的上升子序列。对于一个上升子序列，设结尾位置为 \(x\)，那么子序列中的一个位置 \(y\) 有贡献的条件是一个位置 \(z\) 满足 \(z>y\) 且 \(q_z>q_x\)。
我们只需要用总方案数减去不合法的即可，不合法的条件是不存在 \(z\) 满足 \(z>y\) 且 \(q_z>q_x\)，相当于 \(q_x\) 是 \(q_{y...n}\) 的最大值。
我们对于每个位置 \(i\) 考虑其贡献，设 \(q_{i...n}\) 的最大值位置为 \(w\)，我们要算的就是包含 \(i\) 且以 \(w\) 结尾的上升子序列个数，为 \(q_{1...i}\) 以 \(i\) 结尾的上升子序列个数 \(\times q_{i...w}\) 以 \(i\) 开头以 \(w\) 结尾的上升子序列个数。前半部分好做，注意 \(w\) 是由 \(i\) 更新的，不更新时直接维护，更新时只需要清空树状数组，时间 \(O(n\log n)\)。记录
CF582D Number of Binominal Coefficients
题意：给出质数 \(p\) 和整数 \(\alpha,A\)，求有多少对 \((n,k)\) 满足 \(0\le k\le n\le A\) 且 \(p^\alpha| {n\choose k}\)，答案模 \(10^9+7\)。 \(1\le p,\alpha\le 10^9,\space 0\le A\le 10^{1000}\)
Kummer 定理：\({a+b \choose a}\) 中质数 \(p\) 的次数为 \(a+b\) 在 \(p\) 进制下进位次数。
感性证明：考虑对初始为 \(0\) 的数连续做 \(n\) 次 \(+1\)，在 \(p\) 进制下会进位 \(\lfloor \frac np \rfloor+\lfloor \frac n{p^2} \rfloor +...\) 次，这相当于 \(n!\) 中 \(p\) 的次数。而 \({a+b \choose a}=\frac{(a+b)!}{a!b!}\)，相当于连续 \(a+b\) 次 \(+1\) 的贡献，然后去掉 \(a\) 和 \(b\) 各自进位的贡献。
转 \(p\) 进制就可以直接数位 dp 了。
细节有点多，记录。
CF1103D Professional layer
题意：给出 \(n,k,a_{1...n},e_{1...n}\)，一次性修改 \(x\) 个数（\(x\) 自己定），对于每个修改的数 \(a_i\)，选择 \(a_i\) 的一个约数 \(d\) 修改为 \(\frac{a_i}d\)，使得最终 \(\gcd(a_1,a_2,...,a_n)=1\)，求最小的 \(x\sum\limits_i e_i\)。 \(1\le n\le 10^6,\space 1\le k,a_i\le 10^{12},\space 1\le k\le 10^{12}\)
--
先求出 \(\gcd\)，设为 \(g\)，\(g\) 中质因子最多 \(10\) 个，设实际个数为 \(m\)。
我们只关心 \(a_i\) 中 \(g\) 中的质因子，求出每个质因子的次数。不难发现每个质因子次数都相同的两个数除了 \(e_i\) 是等价的，考虑分为若干个等价类，求出每个等价类的前 \(m\) 小的 \(e_i\) 分别是多少。
搜一下，等价类差不多一万多一些，比较少。
然后直接状压 dp，设 \(f[i,j,S]\) 表示前 \(i\) 个等价类处理的质因子集合为 \(S\)，修改了 \(j\) 个数，最小代价是多少，直接转移即可，时间 \(O(\text{可过})\)。记录
标签：总结,...,2024.2,le,10,字母,合并,26,合法 From： https://www.cnblogs.com/Sktn0089/p/18035706