洛谷题单 . 可以做做 .
有小数的精度要求都是 \(10^{-6}\) 大概 . 图默认是简单图 .
A. コンテスト
给序列 \(\{a_n\}\)，问在 \(\{a\}\) 中选若干数加起来能得到多少不同的数 .
\(1\le n,a_i\le 100\) .
01 背包即可，实现的好的话时间复杂度 \(\Theta(nV/w)\) .
B. ゲーム
两个堆 \(S_1,S_2\)，Alice 和 Bob 轮流操作，每次选一个堆取出堆顶，每个人都想要让自己取出的数之和最大 . 问 Alice 最后取出的数的和是多少 .
两个堆的大小均不大于 \(10^3\) .
比较朴素，类似 AtCoder DP 26 题的 L. Deque，时间复杂度 \(\Theta(n^2)\) .
C. トーナメント
\(2^k\) 个人打淘汰赛（形如一棵满二叉树），其中第 \(i\) 个人 Elo Rating 为 \(r_i\) .
人 \(p\) 和人 \(q\) 对战，人 \(p\) 获胜的概率为 \(\dfrac{1}{1+10^{(r_q-r_p)/400}}\)，问最后每个人获胜的概率 .
\(1\le k\le 10\) .
令 \(dp_{k,i}\) 表示第 \(k\) 轮后第 \(i\) 个人存留的概率，则不难得到转移：
\[dp_{k,i}=dp_{k-1,i}\cdot\sum_{j\in S_{k,i}}\operatorname{prob}(j,i)\cdot dp_{k-1,j} \]其中 \(S_{k,i}\) 表示第 \(k\) 轮能和 \(i\) 比赛的人，\(\operatorname{prob}(j,i)\) 表示 \(j\) 赢 \(i\) 的概率 .
时间复杂度 \(\Theta(k2^k)\) .
D. サイコロ
将一个六面骰子掷 \(n\) 次，问每次掷得点数之积为 \(d\) 的倍数的概率 .
\(1\le n\le 100\)，\(1\le d\le 10^{18}\) .
因为只有六面，所以乘积肯定只有素因子 \(2,3,5\)，那么考虑令 \(dp_{n,a,b,c}\) 表示掷 \(n\) 次，最终 \(2,3,5\) 因子的次数分别为 \(a,b,c\) 的概率 . 那么可以朴素转移 .
时间复杂度 \(O(n\log d)\) .
E. 数
计数 \([1,n]\) 内数位和是 \(d\) 的倍数的数的数量，对 \(10^9+7\) 取模 .
\(1\le n\le 10^{10000}\)，\(1\le d\le 100\) .
和 AtCoder DP 26 题的 S. Digit Sum 是完全一致的题目 .
考虑数位 DP，令 \(dp_{x,e}\) 表示到第 \(x\) 位且目前数位和 \(s\equiv e\pmod d\)（\(0\le e<d\)）的答案，然后可以朴素转移 .
时间复杂度 \(\Theta(d\lg k)\) .
F. 準急
选 \(1\dots n\) 中的若干数，计数选择方案，要求满足：
- 选中 \(1,\,n\) .
- 不能选中连续的 \(k\) 个数 .
对 \(10^9+7\) 取模 .
\(1\le k\le n\le 10^6\) .
令 \(dp_{n,0/1}\) 表示选 \(1\dots n\) 且不选 / 选 \(n\) 的方案数，那么有转移：
\[\begin{aligned}&dp_{n,0}=dp_{n-1,0}+dp_{n-1,1}\\&dp_{n,1}=dp_{n-1,0}+dp_{n-1,1}-dp_{n-k,0}\end{aligned} \]时间复杂度 \(\Theta(n)\) .
G. 辞書順
给一个长为 \(n\) 的字符串 \(S\)，求其字典序第 \(k\) 小的非空子序列，重复（字符串本质不同当且仅当看起来不一样）只算一次，不存在输出
Eel.\(1\le n\le 10^6\)，\(1\le k\le 10^{18}\)，字符集为小写字母 .
不难想到按位考虑，所以其实只需要算 \(i\dots n\) 中强制选 \(i\) 的本质不同子序列数量 .
考虑在子序列自动机上 DP . 具体的，令 \(\operatorname{next}(i,c)\) 表示 \(i\) 之后第一个 \(c\) 的位置，\(dp_i\) 表示 \(i\dots n\) 中强制选 \(i\) 的本质不同子序列数量 . 考虑重复情况只计算选择位置字典序最小的那个，于是可以得到转移：
\[dp_i=1+\sum_c dp_{\operatorname{next}(i,c)} \]不过 \(dp\) 的真实值可能很大，可以和 \(k+1\) 取 min，不会丢失需要的信息 .
时间复杂度 \(\Theta(nS)\)，其中 \(S=26\) 是字符集大小 .
H. ナップザック
\(n\) 个物品，每个物品有质量、价值和颜色 . 要求放入一个背包中，容量上限为 \(w\)，颜色种类数上限为 \(c\)，求最大价值和 .
\(1\le n\le 100\)，\(1\le w\le 10^4\)，\(1\le c\le 50\) .
令 \(dp_{i,j,k}\) 表示选 \(1\dots i\) 中的颜色，选了 \(j\) 种颜色，质量和为 \(k\) 的答案，那么在 \(1\dots i\) 加入 \(i+1\) 肯定颜色种类数多 1，于是就可以简便处理颜色种类数了 . 转移类似 01 背包转即可 .
时间复杂度 \(\Theta(n+wc^2)\) .
I. イウィ
给一个长度为 \(n\) 的仅含
i,w的字符串 \(S\)，每次可以删一个子串iwi，问最多能删几次 .\(1\le n\le 300\) .
令 \(dp_{l,r}\) 表示 \(S[l:r]\) 是否能被删空，可以朴素区间 DP 处理 .
那么把所有 \(dp\) 值为 \(1\) 的区间全部拿出来，就变成了选若干不交区间使得其并的大小最大的问题，可以反悔贪心做 .
经过一些简单分析可以知道时间复杂度为 \(\Theta(n^3)\) .
J. ボール
\(n\) 个物品，第 \(i\) 个在 \(x_i\) 处 . 向坐标 \(x\) 扔球时，均匀随机击中坐标 \(x-1, x, x+1\) 中的一个 . 问在最优策略下期望扔球多少次能打倒所有物品 .
\(1\le n\le 16\)，\(0\le x_i\le 15\) .
令 \(dp_S\) 表示打到 \(S\) 内所有物品的期望步数，则考虑投 \(x\) 位置期望扔多少步：
\[E_{s,x}=1+\dfrac13\sum_{\substack{p\in[x-1,x+1]\cr \{p\}\in S}}dp_{S\setminus\{p\}}+\left(1-\dfrac13\sum_{p\in[x-1,x+1]}[\{p\}\in S]\right)E_{s,x} \]那么解出 \(E_{s,x}\) 后做转移 \(dp_S=\min\limits_x\{E_{s,x}\}\) 即可 .
时间复杂度 \(\Theta(n2^n)\) .
K. ターゲット
如果一组圆满足前面的圆总是严格包含于后面的圆，则称其为一个靶子，且大小为圆的数量 .
现有 \(n\) 个圆，第 \(i\) 个圆心为 \((x_i,0)\)，半径为 \(r_i\) . 问选若干个圆最大可以组成多大的靶子 .
\(1\le n\le 10^5\) .
其实就是若干区间问最多可以嵌多少层，两个区间 \([l_1,r_1],[l_2,r_2]\) 满足条件当且仅当 \(l_1<l_2,\,r_1>r_2\) . 那么按 \(l\) 排序后找最长下降子序列即可 .
时间复杂度 \(\Theta(n\log n)\) .
L. 猫
\(n\) 只猫，第 \(i\) 只在位置 \(x_i\)，满足 \(\{x\}\) 是单调递增的实数序列 . 猫 \(i\) 和猫 \(j\) 的友好指数为 \(f_{i,j}\)，猫 \(i\) 的幸福指数是与其距离不超过 \(1\) 的猫和她的友好指数之和 .
现给定 \(f\)，对于任意序列 \(\{x\}\)，问所有猫幸福指数和的最大值 .
\(1\le n\le 10^3\) .
首先把答案除以 2，那么对于 \(j<i\) 令 \(dp_{i,j}\) 表示 \(i,j\) 距离不超过 \(1\) 时 \(1\dots i\) 的最大答案，则：
\[dp_{i,j}=\max_{k=1}^j\{dp_{i-1,k}\}+\sum_{k=j}^if_{i,k} \]动态记一下前面的 max 就可以 \(\Theta(1)\) 转移了 .
时间复杂度 \(\Theta(n^2)\) .
M. 家
\(h\) 层图，每层图都一模一样，有 \(r\) 个点，从 \(h\) 层的 \(1\) 号点到 \(1\) 层的一号点，每次可以做下列操作之一：
- 沿着边走一步 .
- 层数减一 .
问不经过相同点的方案数，对 \(10^9+7\) 取模 .
\(2\le h\le 10^9\)，\(1\le r\le 16\)，8s .
就是经典问题 AtCoder DP 26 题的 R. Walk 的简单变形 .
首先求出矩阵 \(A\)，其中 \(A_{i,j}\) 是 \(i\) 到 \(j\) 的简单路径条数，则答案即为 \(A^h_{1,1}\) .
\(r\) 比较小，于是 \(A\) 可以状压求 . 时间复杂度 \(\Theta(2^rr^3+r^3\log n)\) .
N. 木
给一棵 \(n\) 个点的树，一种加边顺序是合法的当且仅当任意时刻所有边的端点全部连通 . 求合法加边顺序数，对 \(10^9+7\) 取模 .
\(1\le n\le 10^3\) .
考虑枚举最开始删哪条边，然后划分为两个子树的话就比较容易了，因为有删边顺序是从祖先到后代 . 对于每棵子树分别 DP 求出方案数后合并即可 . 转移可以考虑依次合并子树 .
那么只需要考虑如何合并子树，若子树 \(u,v\) 内的边数分别为 \(e(u),e(v)\)，方案数分别为 \(c(u),c(v)\)，则看成格路计数即可得到合并后的方案数为 \(\dbinom{e(u)+e(v)}{e(u)}c(u)c(v)\) .
时间复杂度 \(\Theta(n^2)\) .
O. 文字列
给序列 \(\{w\}\)，问小写字母 \(c\) 出现 \(w_c\) 次的字符串数量，对 \(10^9+7\) 取模 .
\(0\le w_c\le 10\) .
首先二项式反演，令 \(f_n\) 为钦定 \(n\) 个位置的方案数，那么考虑依次加入每个字母 .
那么整个字符串就被分成 \(\sum w_c-n\) 个连续段，枚举钦定位置数后分成若干连续段，分割方案数可以用组合数描述，那么可以得到转移：
\[f'_n=\sum_{i=1}^n\dbinom ni\dbinom{w_c-1}{w_c-i}f_{n-i} \]那么答案即为：
\[\mathrm{ans}=\sum_{i\ge1}(-1)^if_i \]时间复杂度 \(O((\sum w_c)^2S)\)，其中 \(S\) 是字符集大小 . 应该可以类似分治 FFT 分析的更小点（我没试过）.
P. うなぎ
给一棵 \(n\) 个点的树，求选出 \(k\) 条至少包含两个顶点的链，且任意两条链在顶点上不交的方案数，不一定要覆盖整棵树 .
\(2\le n \le 1000\)，\(1\le k\le 50\)。
令 \(dp_{u,i,s=0/1/2/3}\) 表示 \(u\) 子树内选 \(i\) 条链，其中：
- \(s=0\)：\(u\) 未被链覆盖 .
- \(s=1\)：\(u\) 是一条直链上深度最大的点 .
- \(s=2\)：\(u\) 在一条直链上 .
- \(s=3\)：\(u\) 在一条非直链上 .
转移略，时间复杂度 \(\Theta(nk^2)\) .
Q. 連結
\(n\) 个 01 串 \(\{w_n\}\)，找几个按任意顺序拼接，一个字符串可以选多次，问拼出来的本质不同的长为 \(L\) 的串个数，对 \(10^9+7\) 取模 .
\(1\le n\le 510\)，\(1\le|w_i|\le 8\)，\(1\le L\le 100\) .
和 SDOI2009 学校食堂那个题差不多 .
本质不同比较难处理，那么就考虑一位一位的拼出最终字符串，那么因为字符串长度都比较小，于是只需要维护最近 \(7\) 位的状态和分隔符即可 .
具体的，令 \(dp_{n,S_1,S_2}\) 表示长为 \(n\) 的字符串，最后 \(7\) 位状态为 \(S_1\)，拼接分隔符状态为 \(S_2\) 的串个数，转移相对平凡，不表 .
时间复杂度 \(\Theta(nm+L\cdot 2^{2m})\)，其中 \(m=\max\{w_i\}\)，可以通过 .
R. グラフ
给 \(n\) 个点的有向图，选两条路径（不用简单），最大化被覆盖过的点的总数 . 只需输出最大数量 .
\(1\le n\le 300\) .
首先缩点变成 DAG 上问题 . 考虑加虚拟源汇点 \(s,t\) 后变成找 \(s\) 到 \(t\) 的两条路径 .
于是令 \(dp_{u,v}\) 表示两条路径 \(s-u,\,s-v\) 的最大覆盖总点数，枚举出边转移即可 .
时间复杂度 \(O(n^3)\)，可以通过 .
S. マス目
给一个 \(n\times m\) 网格，将其黑白染色，要求：
- \((1,1),\,(n,m)\) 染黑色 .
- 存在一条从 \((1,1)\) 到 \((n,m)\) 的只经过黑色点的路径 .
求方案数，对 \(10^9+7\) 取模 .
\(2\le n\le 6\)，\(2\le m\le 100\) .
肯定是按列考虑，不过只维护目前列的状态不能统计答案 . 把网格划分为若干黑色连通块，限制就是 \((1,1),\,(n,m)\) 处于同一连通块内，则可以考虑记录从属于连通块的状况 .
具体的，因为只有最多 6 行所以最多 3 个连通块，对于四进制数 \(S\)，0/1/2/3 分别表示白位置，和 \((1,1)\) 连通和两个别的连通块 . \(dp_{n,S}\) 表示处理到前 \(n\) 列，第 \(n\) 列状态为 \(S\) 的方案数 . 注意因为我们只关注 1 所以 2, 3 其实是无序的需要人为钦定一个顺序 . 转移就枚举一列状态并查集维护连通性即可 .
不算并查集复杂度，看起来时间复杂度是 \(O(m8^n)\) 的，也不是不能过 . 不过可以分析到更小一点，暴搜可以知道 \(n=6\) 时合法的状态 \(S\) 的数量 \(\mathsf S(6)=196\)，所以离散化后可以得到准确时间复杂度是 \(\Theta(m2^n\mathsf S(n))\)，这是远小于 \(m8^n\) 的 .
魔王题 . sb，不写代码 .
T. フィボナッチ
如下定义序列 \(\{a\}\)：
\[a_n=\begin{cases}1&n\le k\\\sum\limits_{i=1}^ka_{n-i}&n>k\end{cases} \]给定正整数 \(n,k\)，求 \(a_n\) . 对 \(10^9+7\) 取模 .
\(1\le n\le 10^9\)，\(2\le k\le 10^3\) .
算行列式或者直接看答案 OGF 的分母就知道特征多项式：
\[g(\lambda)=\lambda^k-\lambda^{k-1}-\cdots-1 \]然后暴力做 Fiduccia 算法后面的部分就行了，时间复杂度 \(\Theta(k^2\log n)\) .
标签：10,le,Contest,复杂度,DP,Theta,sum,dp,Typical From： https://www.cnblogs.com/CDOI-24374/p/17398205.html