最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

快播：NOIP动态规划

来源：博客园

动态规划

引入

前言

本blog主要侧重于 \(\text{NOIP}\) 与 \(\text{CSP-S}\) 范围的动态规划相关内容

不包括一般的数据结构优化(没什么技术含量),也不包括任何斜率优化,凸包优化,dp套dp,动态dp,插头dp之类的东西(提高组不考)


(资料图片)

几乎不包括任何知识点的讲解（烂大街了）

仅用于蒟蒻的复习,希望能给大家一点帮助,有错误也欢迎指出

DP常用技巧

  1. 增加维数
  2. 交换答案与状态
  3. 可行解转最优解
  4. 删掉本质相同的状态
  5. 对部分状态\(dp\)
  6. 遇到转移顺序的困难,考虑记忆化搜索
  7. 遇到转移细节过多的问题,考虑从 \(i\rightarrow i+1\) 而不是 \(i-1\rightarrow i\)
  8. 考虑状态时,先把需要记下来的都记一遍,再考虑优化

DP杂题

CF837D （可行性转最优化）

题目

我们把一个数的 roundness 值定义为它末尾 \(0\) 的个数。

给你一个长度为 \(n\) 的数列，要求你从中选出 \(k\) 个数，使得这些选出的数的积的 roundness 值最大。

\(n\ge 200\)

题解

考虑一个很暴力状态，设\(f[i][j][a][b]\)表示考虑到第\(i\)个数，选了\(j\)个，因子\(2\)和\(5\)的个数分别是\(a,b\)的方案是否存在,答案就是对\(f[i][k][a][b]=true\)的状态取\(\min(a,b)\)

我们发现直接这样转移的复杂度是\(\mathcal O(n^4)\)的，无法通过本题。

所以我们考虑套路可行解转最优解，设\(f[i][j][a]\)表示考虑到第\(i\)个数，选了\(j\)个，因子\(2\)个数为\(a\)时因子\(5\)最多是多少

这样子复杂度就降为了\(\mathcal O(n^3)\)，可以通过本题

CF677D （分层图dp）

题目

有一个 \(n\times mn×m\) 的矩阵 \(a(1\le a_{i,j}\le p)\) ，求从起点 \((1,1)\) 出发依次遍历值为 \(1\to p\) 的矩阵单元的最短路径曼哈顿距离。保证满足 \(a_{i,j}=p\) 的 \((i,j)\) 唯一。

数据范围：\(1\le n,m\le 300,1\le p\le n\cdot m\)题解

我们先把数按照种类分组，分成 \(p\) 组。

\(f[i][j]\) 表示到达目前这个数的最短路，那么转移方程为 \(f[i][j] = \min\lbrace f[x][y]+|x-i|+|y-j|\rbrace\)，其中 \((x,y)\) 为上一组中所有数的坐标。

然后要是直接暴力的状态转移的话，是要TLE的，考虑进行优化（下面这个优化真的太神仙了）。

考虑一个界限 \(K\)，假设当前组为 \(\text{T}[i]\)，上一组为 \(\text{T}[i-1]\)，

那么当 \(\text{T}[i].\text{size} \le K\) 时，我们就用继续用上面的暴力动态转移，那么对于所有的“上一组”点数加起来不会差过 \(nm\)，因此总时间复杂度 \(\mathcal O(K \cdot nm)\)；

如果\(\text{T}[i].\text{size} > K\)，我们在网格上进行多源点的优先队列BFS，源点是所有的 \(\text{T}[i-1]\) 组内的点，搜出到所有 \(\text{T}[i]\) 组内的点的最短距离，这样BFS最多跑一遍所有网格，时间复杂度 \(\mathcal O(nm \log(nm))\)；由于这样的组数目不会超过 \(\frac{nm}{K}\) 个，所以总时间复杂度为 \(\mathcal O(\frac{nm}{K} nm \log(nm) )\)。

这样一来，两种加起来的总时间复杂度就是 \(\mathcal O(Knm+\frac{nm}{K}nm\log(nm) ) = \mathcal O( nm (K + \frac{nm\log(nm)}{K}) )\)，由此可知取 \(K=\sqrt{nm \log(nm) }\) 时，时间复杂度最小，为 \(\mathcal O(nm\sqrt{nm\log(nm)})\)

P1004 [NOIP2000 提高组] 方格取数（去除冗余状态）

题意

给定一个 \(n\times m (n,m\le 200)\) 的矩阵,每个格子里有不同的正整数。一个人从左上角走到右下角,走两次,取走两次路径上的数(同一个数不可以重复取),最大化这些数的和

题解

显然我们可以设 \(f[i][j][k][l]\) 表示第一次走到 \((i,j)\) ,第二次走到 \((k,l)\) 时的最大值

考虑如何优化

首先,两次走的总步数一定是 \(n+m\) 的,同理,如果我们控制两次同时走的话,那么有 \(i+j=k+l\) ,这样我们就可以设 \(s=i+j\) 省下一维,转移方程很显然,注意两次相遇的问题即可

BZOJ 1801 中国象棋(DP) （去除不必要的维度）

题目

在\(n\times m\)的棋盘上放若干炮使得不互相攻击。有多少种放法？

说人话就是，不存在三炮共线的情况有多少种

\(n,m\ge 100\)

题解

首先，一个显然的想法是进行状压\(dp\),设\(f[i][s]\)表示考虑到第\(i\)行,\(s\)是一个三进制状态，存每一列都用了多少个炮，这样转移的复杂度是\(3\)的指数级的，显然无法通过

我们考虑一件事，就是假设前\(i\)行的炮都放完了，那么第\(i+1\)行的炮能放的方案数只与剩余了多少位置能放有关，我们并不需要知道这些炮具体放在了什么位置

所以我们可以设\(f[i][j][k]\)表示，考虑完前\(i\)行,有\(j\)列还可以放\(1\)个炮，\(k\)列还可以放\(2\)个炮的总方案数

我们考虑转移

  • 放0个炮，那么就是：
\[　　f[i+1][j][k]\leftarrow f[i][j][k];\]
  • 放1个，可以放在还可以放1个炮的列中，也可以放在还可以放2个炮的列中：
\[\begin{aligned}　　&if (j>=1)　f[i+1][j-1][k]\leftarrow f[i][j][k]*j\\　　&if (k>=1)　f[i+1][j+1][k-1]\leftarrow f[i][j][k]*k\end{aligned}\]
  • 放2个，可以都放在还可以放1个炮的列中，也可以都放在还可以放2个炮的列中，也可以每边放一个：
\[\begin{aligned}　　&if (j>=2)f[i+1][j-2][k]\leftarrow f[i][j][k]*(j*(j-1)/2)\\　　&if (k>=2)f[i+1][j+2][k-2]\leftarrow f[i][j][k]*(k*(k-1)/2)\\　　&if (j>=1 \And k>=1)f[i+1][j][k-1]\leftarrow f[i][j][k]*j*k\end{aligned}\]

[SCOI2008]着色方案 （利用题目性质优化状态）

题目

有 \(n\) 个木块排成一行，从左到右依次编号为 \(1\) 至 \(n\)。

你有 \(k\) 种颜色的油漆，第 \(i\) 种颜色的油漆足够涂 \(c_i\) 个木块。且保证 \(\sum_{i=1}^kc_i=n\)。

统计任意两个相邻木块颜色不同的着色方案

题解

一个变态朴素的想法，我们进行\(15+2\)维的\(dp\),那\(15\)维状态存对应的颜色剩余的个数，但是显然\(5^{15}\)实在无法令人接受

我们意识到一个问题，使相邻木块颜色不同并不需要枚举每一种颜色，事实上，我们只要保证当前颜色不与上一次的颜色相同，那么就是合法的转移，所以我们考虑优化状态

设\(f[i][j][a][b][c][d][e]\)表示考虑到第\(i\)位，上一次选的数还剩\(j\)次可选，剩余\(1,2,3,4,5\)次的数分别还有\(a,b,c,d,e\)个，我们上一次选的这时候我们的状态数就为\(15^{5}\),这比上面那个东西小多了，复杂度是正确的

我们不能选的状态，就是剩余次数为\(j\)的颜色其中一个，直接转移就行

[AGC044A] Pay to Win （记忆化搜索,大力出奇迹）

题目

你需要通过如下操作把 \(0\) 变成 \(N\) \((N \le 10^{18})\)

  • 花 \(\text{A}\) 个金币把数字乘 \(2\) 。
  • 花 \(\text{B}\) 个金币把数字乘 \(3\) 。
  • 花 \(\text{C}\) 个金币把数字乘 \(5\) 。
  • 花 \(\text{D}\) 个金币把数字加一或减一。

求最少需要花费的金币。

题解

倒着记忆化搜索,乘法变成除法,遇到除不尽的通过加法调整

这样形成的就是一个深度为 \(\log N\) 的六叉树

时间复杂度 \(\mathcal O(\text{能过})\)

[USACO2.3]奶牛家谱 Cow Pedigrees （恰好到不超过）

题目

一个有 \(n\) 个节点，深度为 \(k\) 的无标号完满二叉树（即每个节点的儿子数为 \(0\) 或 \(2\)）有多少种结构？定义根节点深度为 \(1\)。

答案对 \(9901\) 取模。

\(3\le n < 200\)，\(2 \le k < 100\)。

题解

考虑到 \(\text{恰好k个}\) 并不好做,所以我们考虑 \(\text{不超过k个}\) 怎么做

设 \(f[i][j]\) 表示点数为 \(i\) ,最大深度不超过 \(j\) 的二叉树的个数

枚举其左儿子大小进行转移即可

复杂度 \(\mathcal O(n^2k)\)

ZR2022 NOIP十连测Day6 T1 跳棋（有向图+tarjan缩点+拓扑排序/记忆化搜索的一类经典套路）

sb出题人卡常数,下面这个做法过不了

题目

在一个无穷大的跳棋棋盘上,放有 \(n\) 个棋子,第 \(i\) 个棋子的坐标为 \((x_i,y_i)\) ,问当前局面下各个棋子分别能够到达多少个位置

题解

考虑将每个棋子的答案分成两部分

  • 周围六格中没有放棋子的部分

    拿 \(\text{map}\) 记一下各个棋子的位置,然后枚举就行, \(\mathcal O(n)\)

  • 连续跳跃的部分

    首先连续跳能够跳到的格子一定不超过 \(6n\) 个,因此能跳的位置连上有向边,边数也是 \(\mathcal O(n)\) 级别的

    然后用 \(\text{tarjan}\) 给有向图缩点,跑拓扑排序或者记忆化搜索得到答案

P7516 [省选联考 2021 A/B 卷] 图函数 （Floyd最短路dp）

PS:因为最短路算法和dp有着千丝万缕的联系,所以我在这里放几道偏图论的题应该问题不大(逃

题目

题解

第一步,拆贡献,我们直接计算每个点对 \(h(G)\) 的贡献

我们考虑一个问题,两个点可以相互到达,就说明了这两个点不在同一个强连通分量中,那么对于点 \(u\) ,我们考虑完前 \(x-1\) 个点之后,后面的图上的点都没有办法走到这 \(x-1\) 个点,因为前 \(x-1\) 个点已然不在强连通分量中,没有必要管了。

那么现在问题转化为,对于前 \(n\) 个图 \(G_1\sim G_n\) 分别求出有多少个点对 \((u,v),u\ge v\) 满足存在不经过 \(< v\) 的点使得两点可以互达

一个点对会对答案的前缀产生贡献,为了使答案最大化,我们贪心地考虑每个点对都通过一条使得其最小编号点最大的路径,差分一下处理即可

那么怎么求解两点间经过的最小编号点呢?仔细一想,这很符合 \(\text{Floyd}\) 算法的转移过程,所以使用 \(\text{Floyd}\) 求解即可

时间复杂度 \(\mathcal O(n^3+m)\) 勉强能冲

P3953 [NOIP2017 提高组] 逛公园 （分层图和spfa最短路dp）

题意

给你一张 \(n\) 个点 \(m\) 条边的有向图,起点为 \(1\) ,终点为 \(n\) ,边有非负边权(可以为 \(0\) )。求解使得 \(\text{dis}(1,n)\le \min\text{{dis}}(1,n)+K\) 的路径数

\(n\le 1\times 10^5,m\le 2\times 10^5,K\le 50\)

题解

神仙题!

由于 \(k\) 值很小,所以考虑建立分层图,设 \(f[i][j]\) 表示 \(\text{dis}(1,i)= \min\text{{dis}}(1,i)+j\) 的方案数,对于一条边 \((u,v,w)\) 转移为

\[f[u][j]\rightarrow f[v][\text{dis}_u+j+w-\text{dis}_v]\]

其中 \(\text{dis}_u\) 代表的是从 \(1\) 到 \(u\) 的最短路

但是,我们发现这个转移在 \(0\) 环的情况下是错误的,若 \(0\) 环出现在最短路图上,则直接导致无解。于是考虑一件事,最短路图在无 \(0\) 环的情况下是个 \(\text{DAG}\) ,因此我们可以对最短路图进行拓扑排序判环,有环则当前层无解,否则拿记忆化搜索直接跑（不用考虑转移顺序多是一件美事）,时间复杂度 \(\mathcal O(mk)\)

P7077 [CSP-S2020] 函数调用（DAG建模+dp）

题目

题解

首先考虑一个性质,如果只存在 \(1\) 操作,那么直接做就行,所以考虑如何将 \(2,3\) 两个操作转化成 \(1\) 操作

关键点在于:

  1. 某个函数被调用后序列被乘k，等价于这个函数被执行k次
  2. 乘法可以使用乘法标记

然后拓扑排序dp处理处理即可

P7962 [NOIP2021] 方差 （差分套路+dp）

题目

给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是：任意选择一个正整数 \(1 < i < n\)，将 \(a_i\) 变为 \(a_{i - 1} + a_{i + 1} - a_i\)。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 \(n^2\) 的结果

其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2\)，其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)

\(1 \le n \le {10}^4\)，\(1 \le a_i \le 600\)

题解

初看这个操作感觉很无厘头是吧?那么试着把它差分吧!

于是我们发现操作等价于交换原数列差分数组中的两个数

然后我们不喜欢那个丑到爆的方差定义,于是设 \(S=\sum_{i=1}^na_i\) ,转移就是

\[\begin{aligned}&n\sum_{i=1}^n(a_i-\frac 1nS)^2\\=&n\sum_{i=1}^na_i^2-(\sum_{i=1}^na_i)^2\end{aligned}\]

还有给定的 \(a_i\) 是单调递增的,所以差分序列是恒大于 \(0\) 的

考虑如何得到最优答案,感性理解一下,答案序列应该是个单谷序列,证明可以考虑调整法,这里不赘述

先将 \(a_i\) 按差分数组排序,然后设 \(f[i][s]\) 表示考虑了前 \(i\) 个数,\(\sum a_i=s\) 时最小的 \(\sum a_i^2\) 是多少,分类讨论当前数应该放在前面还是后面,于是有

\[\begin{aligned}f[i-1][s]+(\sum_{j=1}^ib_j)^2 \rightarrow f[i][s+\sum_{j=1}^ib_j]\\f[i-1][s]+i\times b_i^2+2b_i \times s\rightarrow f[i][s+b_i\times i]\end{aligned}\]

时间复杂度 \(\mathcal O(n^2a)\)

P7961 [NOIP2021] 数列 （跟二进制进位有关的dp）

题面

给定整数 \(n, m, k\)，和一个长度为 \(m + 1\) 的正整数数组 \(v_0, v_1, \ldots, v_m\)。

对于一个长度为 \(n\)，下标从 \(1\) 开始且每个元素均不超过 \(m\) 的非负整数序列 \(\{a_i\}\)，我们定义它的权值为 \(v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}\)。

当这样的序列 \(\{a_i\}\) 满足整数 \(S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}\) 的二进制表示中 \(1\) 的个数不超过 \(k\) 时，我们认为 \(\{a_i\}\) 是一个合法序列。

计算所有合法序列 \(\{a_i\}\) 的权值和

\(1 \leq k \leq n \leq 30\)，\(0 \leq m \leq 100\)，\(1 \leq v_i < 998244353\)。

题解

由于有进位的情况出现,因此考虑从低位向高位dp

设 \(f[i][j][k][l]\) 表示考虑到第 \(i\) 位,确定了 \(a\) 序列中的前 \(j\) 个元素,有 \(k\) 个 \(1\),到下一位有 \(p\) 的进位,考虑给 \(S\) 的第 \(i\) 位贡献了 \(p\) 位,那么转移就为

\[f[i+1][j+p][k+(p+l)\% 2][\lfloor\frac{l+p}{2}\rfloor]\leftarrow f[i][j][k][l]\times v_i^p \times \binom{n-j}{p}\]

时间复杂度 \(\mathcal O(n^4m)\)

P6758 [BalticOI2013] Vim（线头dp）

原作者题解,这里引用一下LOJ2687 BalticOI2013 Vim 线头DP,因为原作者写的实在是太好了,所以这里建议去原作者博客获得更好的阅读体验,放这里是方便笔者自阅

题目

题解

原题等价于：给出一个序列和两种移动方式，移动过程中必须要经过某一些点，求最小代价。

把连续的f操作和连续的h操作看成线，那么移动路线如下

首先，考虑下面两种移动路线

显然A路线一定没有B路线优

上面的条件等价于对于某一个位置 \(i\)，经过的位置覆盖了位置 \(i\) 与 \(i+1\) 之间的线段的线的数量要么是 \(1\) ，要么是 \(3\) ，对应下图的 AB 两种情况。

设 \(p_{i,j}\) 表示覆盖了 \(i\) 与 \(i+1\) 之间的线段 \(1\) 次，且 \(f\) 操作选择字符 \(j\) 的最小代价，\(q_{i,j,k}\) 表示覆盖了 \(i\) 与 \(i+1\) 之间的线段 \(3\) 次，且在进行 \(h\) 操作之前的 \(f\) 操作选择的字符是 \(j\)、在进行 \(h\) 操作之后的 \(f\) 操作选择的字符是 \(k\) 的最小代价

又设 \(s_i\) 表示字符串的第 \(i\) 个字符，\(\text{imp}_i\) 表示原串中第 \(i\) 个字符前是否存在字符 \(e\)

转移：

\[\begin{aligned}p_{i,j} = & p_{i-1,j} & j \neq s_i \&\& \text{imp}_i \neq 1\\& p_{i-1,s_i} + 2 \\& q_{i-1,s_i,j} & j \neq s_i \\ & q_{i-1,s_i,s_i} + 2 \end{aligned}\]

\(p_{i,j}\) 的转移分别对应下图的ABCD情况

其中虚线表示新加入的线，红色字表示对应位置的字符类型，黑色字表示位置编号

\[\begin{aligned} q_{i,j,k} = & p_{i-1,j} + 3 & j \neq s_i \\ & p_{i-1,s_i}+5 \\ & q_{i-1,j,k} + 1 & j \neq s_i \&\& k \neq s_i \\ & q_{i-1,s_i,k} + 3 & k \neq s_i \\ & q_{i-1,j,s_i} + 3 & j \neq s_i \\ & q_{i-1,s_i,s_i} + 5 \end{aligned}\]

\(q_{i,j,k}\) 转移分别对应下图中的ABCDEF情况转移就是把线延长和补全的过程，所以叫做线头DP

序列dp

LCS问题

题目1

给定 \(A,B\) 两个排列,求它们的 \(\text{LCS}\)

题解1

两个序列都是排列,那么可以考虑建立映射关系跑LIS

题目2

给定 \(A,B\) 两个序列,求它们的 \(\text{LCS}\)

题解2

就是个简单的多序列dp

设 \(f[i][j]\) 表示考虑了 \(a\) 序列的前 \(i\) 个数, \(b\) 序列前 \(j\) 个数的最长公共子序列的长度,转移显然是

\[f[i][j]=\max\lbrace f[i-1][j],f[i][j-1],f[i-1][j-1]+[i=j]\rbrace\]

CF314E Sereja and Squares（括号序列问题套路1）

题目

给定一个长度为 \(n\) 的仅包含左括号和问号的字符串，将问号变成左括号或右括号使得该括号序列合法，求方案总数

题解

  • 括号序列问题，往往就是把左括号看成 \(+1\) ，右括号看成 \(-1\) ，我们只需要保证任意一个前缀大于等于 \(0\)，且总和为 \(0\) ，就代表是个合法括号序列了

令 \(f[i][j]\) 表示当前到第 \(i\) 个字符，现在还有 \(j\) 个左括号,那么分三种情况考虑

  1. 若第 \(i+1\) 个字符是左括号，则能转移到 \(f[i+1][j+1]\)。
  2. 若第 \(i+1\) 个字符是右括号，则能转移到 \(f[i+1][j-1]\)。
  3. 若第 \(i+1\) 个字符是问号，则能转移到 \(f[i+1][j-1]\) 与 \(f[i+1][j+1]\)

对于这个问题,只需要考虑 \(1,3\) 转移,最终 \(f[n][0]\) 就是方案总数，时间复杂度为 \(\mathcal O(n^2)\)

BZOJ4922 Karp-de-Chant Number（括号序列问题套路2）

题目给出一些括号序列，要求选择一些括号序列拼接成一个合法的括号序列，使得总长最大

长度与个数均不超过 \(300\)

题解

首先将每个括号序列合法的括号对进行一个消除,那么最终得到的括号序列一定形如 $ ))) \cdots (($,于是我们对每个括号序列记两个值 \(x,y\) 表示左括号与右括号的个数,于是我们就是要最大化我们的括号序列配对数,参考上一题,我们在选择括号序列的同时,一定要保证所有时刻的 \(x-y\ge 0\),且最终的 \(x-y=0\)

这像极了P4025 [PA2014]Bohater,这里简述一下贪心思路:

  1. 先排 \(x-y\le 0\) 的,再排 \(x-y<0\) 的
  2. 对于 \(x-y\le 0\) 的,按照 \(y\) 从小到大排
  3. 对于 \(x-y< 0\) 的,倒着考虑,发现本质是将上一种情况的 \(x,y\) 对换了,按照 \(x\) 从到小排即可

转移和上题大同小异,不在赘述

P4933 大师（特殊的子序列提取问题）

题目

给定一个长度为 \(n\) 的非负整数数列,求它有多少个等差子序列。最大值 \(v\) 不超过 \(2\times 10^4\)

题解

一个朴素的想法是,设 \(f[i][d]\) 表示考虑到第 \(i\) 个数,公差是 \(d\) 的子序列的个数,转移显然有

\[f[i][d]=\sum_{j时间复杂度是 \(\mathcal O(n^2v)\) 的,但是我们发现,以 \(i\) 结尾的等差数列的数量是明显不超过 \(i-1\) 的,所以我们考虑给转移方程换一种写法

\[f[i][a_i-a_j]=\sum_{j于是时间复杂度降为 \(\mathcal O(n^2)\) ,空间复杂度为 \(\mathcal O(nv)\) ,可以通过本题

P1874 快速求和（子段划分+背包）

题目

给定一个数字串 \(S~(S\le 40)\) ,要求加入最少的加号来使其变成一个数 \(t~(t\le 1\times 10^6)\) ,求这个最小值,无解输出 \(-1\)

题解

记 \(f[i][s]\) 表示考虑了前 \(i\) 个位置的数,最终构成的数为 \(s\) 的最小值,\(\text{cost}[i][j]\) 表示从 \(i\) 到 \(j\) 构成的数的值,于是有转移方程为

\[f[i][s]=1+\min_{j从后往前枚举 \(j\),超过 \(t\) 便不再继续,时间复杂度为 \(\mathcal O(nt\log t)\)

P2758 编辑距离（经典多序列问题）

题目

给定字符串 \(A,B\),可以对 \(A\) 进行如下操作

  1. 插入一个字符
  2. 删除一个字符
  3. 将一个字符替换成另一个字符

求将 \(A\) 变化成 \(B\) 的最小步数

字符串长度不超过 \(1000\)

题解

设 \(f[i][j]\) 表示将 \(A\) 字符串的前 \(i\) 个字符转化成 \(B\) 字符串中的前 \(j\) 个字符所需要的最小操作次数,转移如下

\[f[i][j]=\min\lbrace f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+[i\not ={j}]\rbrace\]

具体解释下的话是

  1. \(f[i-1][j]\) : \(A\) 的前 \(i-1\) 位与 \(B\) 的前 \(j\) 位对上了,现在要在 \(A\) 中删除一个字符
  2. \(f[i][j-1]\) \(A\) 的前 \(i\) 位与 \(B\) 的前 \(j-1\) 位对上了,现在要在 \(A\) 中插入一个字符
  3. \(f[i-1][j-1]\) 直接把 \(A_i\) 变成 \(B_j\),或者不用变

P2679 [NOIP2015 提高组] 子串

题目

有两个仅包含小写英文字母的字符串 \(A\) 和 \(B\)。

现在要从字符串 \(A\) 中取出 \(k\) 个互不重叠的非空子串，然后把这 \(k\) 个子串按照其在字符串 \(A\) 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 \(B\) 相等？

\(1\le n\le 1000,1\le m\le 200,1\le k\le m\)

题解

设 \(f[i][j][k]\) 表示 \(A\) 串考虑到第 \(i\) 位,匹配到 \(B\) 串的第 \(j\) 位,选了 \(k\) 个字符时的方案数

但是,观察样例, \(\underline{aa}\) 和 \(\underline{a}~\underline{a}\) 是两种方案,因此我们给我们的状态新增一维成 \(f[i][j][k][0/1]\) 表示第 \(i\) 位选还是不选

于是有

\[\begin{cases}f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]\\ f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]~~~(a[i]=b[j])\end{cases}\]

滚掉 \(i\) 这一维,时间复杂度是 \(\mathcal O(nmk)\) ,空间复杂度是 \(\mathcal O(mk)\)

P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落 （回文串问题转成最长公共子序列问题）

题目

给定一个长为 \(n~(n\le 1000)\) 的字符串,要求在其中插入字符使得其成为一个回文串,最小化插入的字符数

题解

一种sb做法是,设 \(f[l][r]\) 表示区间 \([l,r]\) 成为回文串所需要的最下插入数,然后讨论一下就行

if(s[l]==s[r]) f[l][r]=f[l+1][r-1];else f[l][r]=min(f[l+1][r],f[l][r-1])+1;

一种比较优美的做法是,我们令原来的字符串为 \(A\) ,其翻转后的字符串是 \(B\) ,那么这个问题与求 \(A,B\) 的最长公共子序列是等价的

那么我们求出 \(\text{LCS}\) 后拿字符串长度减去 \(\text{LCS}\) 的长度就是答案

CF568E Longest Increasing Subsequence （最大化最长上升子序列长度+dp方案输出）

题目

给定一个长度为 \(n\) 的有 \(k\) 个空缺的序列。

你有 \(m\) 个数可以用于填补空缺,且不可以使用相同的数

要求最大化最长上升子序列的长度。

\(n, m \le 10^5\)，\(k \le 10^3\)

题解

首先,由于两个同样的元素填到序列里面对答案是没有任何贡献的,因此我们得到最优填法所使用的数必然两两不同

设 \(l[i],p[i]\) 表示考虑到第 \(i\) 位时最长上升子序列的长度和上一项的位置,\(f[i],g[i]\) 表示长度为 \(i\) 的上升子序列的最后一项的最小值和它所在的位置,假设我们现在从前向后考虑到第 \(i\) 个位置

  • 若该位置上的数为 \(x\) ,那么在 \(f[i]\) 上二分找到 \(
  • 若该位置是空缺的,枚举我们要填补的数为 \(x\) 找到填补空缺的数中 \(

考虑如何还原,由于我们求 \(LIS\) 的DP过程中是将 \(i\) 作为了一个 \(LIS\) 的终止节点,所以我们自然可以考虑倒序还原

若该位置是空缺的，则先在它前面的不是空缺的位置里找到位置 \(\text{pos}\) 满足 \(l[\text{pos}] = i - 1\) ,同时 \(\text{pos}\) 上的数 \(< x\)。如果找到了，那么上一项的位置就是 \(\text{pos}\) ;否则，上一项的位置就是上一个空缺的位置，且这个空缺上的数为用于填补的数中 \(< x\) 的最大的数

时间复杂度 \(\mathcal{O} (n\log n+m\log m+(n+m)k)\)

HDU 1421 搬寝室 （通过特殊性质将分组问题转为dp问题）

题目

有 \(n\) 个行李,每个行李有一个重量。

在你要去搬行李,要搬 \(2k\) 个行李,每次要搬 \(2\) 个,假设这两次搬得行李的重量为 \(x,y\) ,那么我们称这一次搬行李的疲惫度为 \((x-y)^2\)

要求最小化疲惫度之和

\(2\le 2k \le n\le 2000\)

题解

首先我们注意到dp是很难做 \(2k\) 个物品进行分组的问题的,所以我们要考虑挑了 \(2k\) 个行李出来之后怎样分组是最优的

假设有 \(4\) 个行李的重量从小到大分别为 \(a,b,c,d\) ,我们发现, \((a,b),(c,d)\) 这样分组一定是更优的,证明可以考虑作差法,不再赘述

于是我们设 \(f[i][j]\) 表示考虑完前 \(i\) 个数,选出了 \(j\) 对的方案数,先对 \(n\) 个数升序排序,然后通过分讨选不选 \(i\) 进行转移

  1. 如果将第 \(i\) 个数试做一对中较大的那个数,那么显然它与 \(i-1\) 配对是一定是比跟前面的数配对更优的,同时如果此时要求配成 \(j\) 对,那么就就要保证前 \(i-2\) 个数可以配成 \(j-1\) 对,于是我们的转移如下
\[f[i][j]=f[i-2][j-1]+(a[i]-a[i-1])^2\]
  1. 如果不选第 \(i\) 个数,那么转移如下
\[f[i][j]=f[i-1][j]\]

时间复杂度 \(\mathcal{O}(n^2)\)

BZOJ 1786 配对 （最小化逆序对数）

题目

给你一个长度为 \(n\) 的序列,现在有一些位置未知,要求在这些未知位置上填数,使得最终序列产生的逆序对数最小

保证所有的数都在 \([1,k]\) 范围, \(k\) 给定

\(n\le 1\times 10^4,k\le 100\)

题解

首先考虑一个性质,我们填进去的数一定是单调不降的,证明可以考虑交换填进去的两个数 \(a,b\) ,交换完之后, 中间的数的逆序对是 \(\ge a\) 的数加上 \(\le b\) 的数,由于 \(a\le b\) ,那么这显然比交换前的逆序对数更大。

所以我们每填进去一个数只会对被最开始序列中就有的那些数贡献逆序对数,假设我们填的数是 \(j\) ,那么求一下前缀 \(\ge j\) 的数的个数加上后缀 \(\le j\) 的数的个数即可,可以预处理一下

时间复杂度 \(\mathcal{O}(nk)\)

背包dp

[BJOI2019] 排兵布阵 （背包dp与贪心）

题目

小 C 正在玩一款排兵布阵的游戏。在游戏中有 \(n\) 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 \(m\) 名士兵，可以向第 \(i\) 座城堡派遣 \(a_i\) 名士兵去争夺这个城堡，使得总士兵数不超过 \(m\)。

如果一名玩家向第 \(i\) 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 \(i\) 分。

现在小 C 即将和其他 \(s\) 名玩家两两对战，这 \(s\) 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 \(s\) 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

\(1\le s \le 100\)\(1\le n \le 100\)\(1\le m \le 20000\)对于每名玩家 \(a_i \ge 0\)，\(\sum\limits_{i=1}^n a_i \le m\)

题解

设 \(f[i][j]\) 表示第 \(i\) 个城堡时，已派出 \(j\) 个士兵。

贪心派出恰好严格大于某一玩家派出的数量的两倍。可以排序预处理出 \(g[i][k]\) 表示第 \(i\) 个城堡，出兵数量第 \(k\) 大的人出兵数量

转移方程即为：

\[f[j]=\max\lbrace f[j-g[i][k]*2-1]+k*i,f[j]\rbrace\]

2022牛客OI赛前集训营 Day5 T3 子集 （推式子+背包意义的转换）

题目

给定一个正整数 \(M\) ,对于集合 \(S\) 定义

\[F_0(S)=\left[\sum_{x\in S}=M\right]\]

同时有

\[F_k(S)=\sum_{T\subseteq S}F_{k-1}(T)~~~(k\ge 1)\]

给定集合 \(S=\lbrace a_1,a_2,\cdots,a_n\rbrace\) 和一个正整数 \(k\) ,求\(F_k(S)\)

\(n,M,a_i\le 5000\)

题解

一眼丁真,应该是个背包,但是这 \(k\) 次子集求和比较的麻烦

遇事不决就打表,我们发现了一个规律:

\[F_k(S)=\sum_{T\subseteq S}F_0(T)k^{n-|T|}\]

考虑归纳法证明这个东西

首先 \(k=1\) 的时候,显然成立

若 \(k\) 时成立,则 \(k+1\) 时有

\[\begin{aligned}F_{k+1}(S)=&\sum_{T\subseteq S}F_{k}\\=&\sum_{T\subseteq S}\sum_{C\subseteq T}F_0(C)\cdot k^{|T|-|C|}\\=&\sum_{C\subseteq S}F_0(C)\cdot \sum_{i=0}^{|S|-|C|}\binom{|S|-|C|}{i}k^i\\=&\sum_{C\subseteq S}F_0(C)\cdot (k+1)^{|S|-|C|}\end{aligned}\]

于是我们证明了我们的猜想,那么这个问题就变成了一个01背包的问题,设 \(f[i][j][x]\) 表示考虑到第 \(i\) 个数,一共选了 \(j\) 个数,这些数的和是 \(x\) 的方案数,最后对应的 \(j\) 乘上 \(k^{n-j}\) 即可,时间复杂度是 \(\mathcal O(n^2M)\) 的,无法通过本题

但事实上,仔细想一想我们dp的状态是有冗余的,所以我们考虑更改dp的定义,设 \(f[i][j]\) 表示考虑了前 \(i\) 个数,和为 \(j\) 时对答案的贡献,初始状态 \(f[0][0]=k^n\) 表示空集的贡献,转移时每增加一个物品就在原来的那个位置的基础上除一个 \(k\) ,除此之外这就是一个01背包,代码如下

f[0]=ksm(k,n);for(int i=1;i<=n;++i)for(int j=M;j>=a[i];--j){f[j]+=f[j-a[i]]*inv%mod;f[j]%=mod;}

我们相比原来去除掉了选取个数这一个冗余状态,最后这个东西的时间复杂度是 \(\mathcal O(nM)\) 的

P4141 消失之物 （对背包转移的理解）

题目

有 \(N\) ( \(N\le 2000\) ) 个物品，体积分别是 \(w_1, w_2 ,\cdots, w_N\)

对于每个 \(i\) 与 \(x\) 求：不使用第 \(i\) 个物品能有多少种恰好装满体积为 \(x\) 的背包。

其中 \(x\) 在 \(1\) 到 \(M\) ( \(M \le 2000\) ) 之间

题解

暴力是 \(\mathcal O(n^2m)\) 做 \(n\) 次背包

考虑少了某个物品怎么办

考虑在01背包DP时会用到的这个转移

for(int j=m;j>=w[i];--j)    f[j]+=f[j-w[i]];

我们少了i物品就是在原来的基础上少了一次这样的转移,因此

memcpy(g,f,sizeof f);for(int j=w[i];j<=m;++j)    g[j]-=g[j-w[i]];

处理一下就行

有趣背包问题（交换值域与状态）

题目

初始有 \(m\) 块钱，\(n\) 个物品，其中第 \(i\) 个物品花费 \(\text{cost}[i]\) 块钱，价值为 \(\text{val}[i]\),我们现在想要知道我们用这些钱能买到最多多少价值的东西。

\(n\le 100,1\le \text{val}[i]\le 5,1\le \text{cost}[i],m\le 10^9\)

题解

一般的背包问题是设 \(f[i][j]\) 表示考虑到第 \(i\) 个物品,有 \(j\) 的花费所能取得的最大价值,但是此题的最大花费太大,无法放到状态中

所以我们考虑设 \(f[i][j]\) 表示考虑到第 \(i\) 个物品,产生 \(j\) 的价值所需要的最小花费,找 \(\text{cost} \le m\) 中最大的 \(j\) 即可。

P2340 [USACO03FALL]Cow Exhibition G （可行性转最优化）

题意

有 \(n\) 个物品,第 \(i\) 个物品有 \(a_i,b_i\) 两种花费,可以为负,价值为两者之和,要求在满足每项总花费大于 \(0\) 的情况下,最大化价值

\(n\le 400 |a_i|,|b_i|\le 1000\)

题解

一个朴素的想法是,设 \(f[i][a][b]\) 表示考虑到第 \(i\) 个物品,前者的总花费为 \(a\) ,后者的总花费是 \(b\) 的情况下,是否存在这样一种方案,但是这太sb,所以考虑可行性转最优化

设 \(f[i][a]\) 表示在考虑到第 \(i\) 个物,前者花费是 \(a\) 的情况下 \(b\) 的最大值,那么这就是一个朴素的01背包了,直接转移就行

P1941 [NOIP2014 提高组] 飞扬的小鸟 （背包建模）

题面

题解

设 \(f[i][j]\) 表示横坐标为 \(i\) 时高度为 \(j\) 的最少点击次数，转移方式如下:

  • 上升为完全背包
  • 下降为01背包
  • 越界就特判

时间复杂度 \(\mathcal{O}(n\times m)\)

P1064 [NOIP2006 提高组] 金明的预算方案 （依赖背包）

题面

题解

大力分讨即可

  1. 不选，然后去考虑下一个
  2. 选且只选这个主件
if(j>=v[nw]) f[j]=max(f[j],f[j-v[nw]]+val[nw]);
  1. 选这个主件，并且选附件1
if(j>=v[nw]+v[v1]) f[j]=max(f[j],f[j-v[nw]-v[v1]]+val[nw]+val[v1]);
  1. 选这个主件，并且选附件2
if(j>=v[nw]+v[v2]) f[j]=max(f[j],f[j-v[nw]-v[v2]]+val[nw]+val[v2]);
  1. 选这个主件，并且选附件1和附件2
if(j>=v[nw]+v[v1]+v[v2]) f[j]=max(f[j],f[j-v[nw]-v[v1]-v[v2]]+val[nw]+val[v1]+val[v2]);

时间复杂度同01背包

BZOJ3163 [HEOI2013] 新背包问题（分治+背包）

题目

\(N\) 个物品，第 \(i\) 个物品有 \(c[i]\) 个，购买第 \(i\) 个物品需要 \(a[i]\) 元，可获利 \(b[i]\) 的价值。有 \(m\) 个询问，每次询问：如果第 \(x\) 个物品禁止购买，你有 \(y\) 元的话，能获得的最大价值是多少？询问之间互相独立。

\(N\le 1000,m\le 3\times 10^5\)

题解

初始 \(\text{solve}(1,n)\)

  • 递归的函数到 \(\text{solve}(l,r)\)，维护的dp数组，记录的是除去 \([l,r]\) 外的物品的构成的背包数组。
  • \(\text{solve}(l,mid)\) 时，把 \([mid+1,r]\) 内的物品加入dp数组。

我们这里定义的加入这个物品 \(u\) ，就是多考虑上这个物品之后构成的dp数组，也就是直接按照多重背包的方式转移就好

当 \(l=r\) 时，将对应所有的询问在dp数组查询即可

单调队列优化时复杂度 \(\mathcal O(nw\log n)\) ,每个物品被加进去 \(\log\) 次，每次 \(\mathcal O(w)\)

可行性背包问题（bitset优化）

题目

给出 \(n\) 个物品，每个物品有体积 \(v[i]\) ，要求把物品分成两堆，然后使得两堆物品体积的差的绝对值最小。

\(n,v[i]\le 100\)

题解

我们设总体积为$ \text{sum} $，那么我们必定会存在一堆体积和是小于等于 \(\text{sum}/2\)的，然后就是要求去选出一些物品总体积小于等于 \(\text{sum}/2\) ，最大能取到的体积是多少。

这就是经典的背包问题了,同时可行性的背包问题可以 \(\text{bitset}\) 优化

P1272 重建道路 （树形背包）

题面

给你一颗 \(N\) 个点的树,要求从其中断开几条边,使得分离出一个大小为 \(P\) 的子树,要求最小化边数

题解

设 \(f[u][s]\) 表示以 \(u\) 为根的子树保留大小为 \(s\) 的子树所需要的最小花费

初始化:

\[f[i][0]=0,f[i][1]=\text{与}i\text{相邻的点数}\]

转移

\[f[u][s]=\min_{v\in\text{son}_u}\lbrace f[u][k]+f[v][s-k]-2\rbrace\]

注意我们的状态设计,连接 \(u,v\) 的边被消除了两次,所以要减 \(2\)

化学反应（二维背包dp）

题面

给出 \(n\) 个化学反应，每个反应消耗 \(a[i]\) 升氧气和 \(b[i]\) 升氢气，可以得到 \(w[i]\) 的价值，现在总共有 \(X\) 升氧气和 \(Y\) 升氢气，求我们最多可以得到多少价值

题解

设 \(f[i][x][y]\) 表示前 \(i\) 个物品，消耗了 \(x\) 的氧气和 \(y\) 的氢气所能得到的最大收益是多少。

然后考虑一个物品选还是不选即可

vijos1240 （根据题目性质给背包增维）

题目

  1. 给你一些房间，告诉你这些房间的容纳人数和价格。

  2. 安排一定数量的人住到旅馆里，满足：

    不同性别的人如果不是夫妻那么不能住一个房间。一对夫妻如果住在一起，那么房间不能安排其他的人进去哪怕房间没盛满人

  • 你来写一个程序帮助佳佳找到安排这些来参加旅行的人住进旅馆所需要的最小花费。
  • \(M\)：参加旅行的男性人数、 \(f\)：参加旅行的女性人数、 \(r\)：旅馆的房间数、\(c\)：这些男女中有多少对夫妻、\(B_i\)：每个房子容纳人数和、\(P_i\)：每个房子价格。注意每一个人不是单身就是和他/她唯一的妻子/丈夫一起参加旅行。\(0\le m,f,r\le 300，0\le c\le \min(m,f)，0\le P_i\le 10 2\le B_i\le 300\)

题解

首先考虑一件事情:如果有两对及以上夫妻,那么拆开分别住一定不会比他们在一起更劣

因此,要么只有一对夫妻,要么没有

于是,设 \(f[i][j][k][0/1]\) 表示考虑到第 \(i\) 号房间,有 \(j\) 个男性和 \(k\) 个女性,是否存在一对夫妻时的最小花费

\[f[i,j,k,0]=\min\lbrace f[i-1,j,k,0],f[i-1,j-v[i],k,0]+p[i],f[i-1,j,k-v[i],0]+p[i]\rbrace \\◦f[i,j,k,1]=\min\lbrace f[i-1,j,k,1],f[i-1,j-v[i],k,1]+p[i],f[i-1,j,k-v[i],1]+p[i],f[i-1,j-1,k-1,0]+p[i]\rbrace \]

P3188 [HNOI2007]梦幻岛宝珠 （通过特殊条件缩小范围）

题面

给你 \(N\) 颗宝石，每颗宝石都有重量和价值 \(V\) 。要你从这些宝石中选取一些宝石，保证总重量不超过 \(W\) ,并输出最大的总价值，每颗宝石的重量符合 \(a\times 2^b\)。\(V\le 1\times 10^9,a\le 10,b\le 30\)

题解

首先,这道题的数据范围及其的吓人,但是注意到 \(a\) 的范围很小,所以我们可以根据 \(b\) 做分层dp

设 \(f[i][j]\) 表示第 \(i\) 层的背包花费为 \(j\) 时的最大价值,直接01背包转移即可

难点在于如何合并每一层的背包,设 \(g[i][j]\) 表示考虑到前 \(i\) 层物品体积小于等于\(j\times 2^i+W\And (1<<(i-1))\) 时的最大价值,转移如下

\[g[i][j]=\max_k\lbrace f[i][j-k]+g[i-1][2\times k+(W>>(i-1))\And 1]\rbrace\]

感性理解一下,这个过程就是高位把它的空间分给了低位,所以要乘 \(2\) ,与此同时,背包里本来就有供低位使用的空间,所以要加上

注意到 \(n\le 100,a\le 10\) ,所以重量最多就记到 \(1000\) 就行了,时间复杂度 \(\mathcal O(an^2)\)

LOJ6089 小Y的背包计数问题 （剩余系分类与处理不降序列的方法）

题目

小Y有一个大小为 \(n\) 的背包，并且小Y有 \(n\) 种物品。

对于第 \(i\) 种物品，共有 \(i\) 个可以使用，并且对于每一个 \(i\) 物品，体积均为 \(i\) 。

求小Y把该背包装满的方案数为多少

定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。

\(n\le 1\times 10^5\)

题解

首先有个显而易见的性质:大小 \(\ge \sqrt n\) 的物品不可能被选完

因此我们的问题变成前 \(\sqrt n\) 个是多重背包,后面的都是完全背包

  • 对于前 \(\sqrt{n}\) 个数

我们可以直接多重背包做吗? \(\mathcal O(n\log n \sqrt n)\) 的复杂度是无法接受的,考虑优化转移

\[f[i][j]=\sum f[i-1][j-ki]\]

我们发现每次都是从 \(j\mod i\) 的剩余系中转移而来,因此依照剩余系分类,前缀和优化转移,时间复杂度降为 \(\mathcal O(n\sqrt{n})\)

  • 对于后面的数

首先,我们依次选择 \([\sqrt{n},n]\) 的物品,最终这些物品会形成一个单调不降的序列,那么我们有一种经典的计算所有不降序列的方法

  1. 在最前方加入一个大小为 \(\sqrt{n}\) 的数
  2. 让已经加入的所有数加 \(1\)

这样就可以考虑到所有的不降序列的,具体转移为

\[g[i][j]=g[i-1][j-\sqrt{n}]+g[i][j-i]\]

其实， \(g[i][j]\) 对应的就是原问题中选了前 \(i\) 个物品，总体积为 \(j\) 的方案数。有了这些，我们就可以统计答案了。设 \(\text{sum}[i]=\sum_{j=\sqrt{n}+1}^{n} g[j][i]\) ，那么答案就是

\[\text{Ans}=\sum_{i=0}^{n}f[\sqrt{n}][i]\times \text{sum}[n-i]\]

整数划分模型

  1. 求把 \(n\) 划分成 \(k\) 个正整数的方案数？
  2. 求把 \(n\) 划分成互不相同 \(k\) 个正整数的方案数？
  3. 求把 \(n\) 划分成 \(k\) 个不大于 \(m\) 的互不相同正整数的方案数？
  4. 求把 \(n\) 划分成 \(k\) 个奇数/偶数的方案数？

问题1

设 \(f[i][j]\) 表示数 \(i\) 分解成 \(j\) 个正整数的方案数,转移时分为两种情况

  1. 给数 \(i-j\) 所有的 \(j\) 划分的每个数加 \(1\),即 \(f[i][j]\leftarrow f[i-j][j]\)
  2. 给数 \(i-j\) 所有的 \(j-1\) 划分的末尾填上 \(1\),即 \(f[i][j]\leftarrow f[i-1][j-1]\)

理解一下这其实可以讨论到所有的情况

问题2

状态与上一题是一致的,转移如下

\[f[i][j]=f[i-j][j]+f[i-j][j-1]\]

因为要限制没有相同的数字,所以填数的时候必须先给其他所有数加上 \(1\) 之后再填 \(1\) 就不会有相同的情况出现了

问题3

转移方程改成

\[f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-(m+1)][j-1]\]

减去多余的部分即可

问题4

设 \(f[i][j]\) 表示将 \(i\) 划分成 \(j\) 个奇数的方案数, \(g[i][j]\) 表示将 \(i\) 划分成 \(j\) 个偶数的方案数,那么有

\[g[i][j]=f[i-j][j]f[i][j]=f[i-1][j-1]+g[i-j][j]\]

CF366C Dima and Salad（分数规划问题与背包）

题目

有 \(n\) 个水果，每个水果有两个属性：美味值和卡路里值。现在选用若干个（至少 \(1\) 个）水果制作一份特殊的沙拉，沙拉的美味值为所选的水果的美味值的和，沙拉的卡路里值为所选水果的卡路里值的和。沙拉的美味值恰好是卡路里值的 \(K\) 倍。请计算该沙拉美味值最大为多少。

题解

根据 \(a[i] - \text{k}b[i] = 0\) ,我们可以将其看作是一个背包问题，\(a[i]\) 当作是价值，\(a[i]-\text{k}b[i]\) 当作是重量 ,\(0\) 为容量,然后做就行了

\(n\le 100 ,k \le 10\)

CF755F PolandBall and Gifts（贪心+背包）

题目

圣诞节到了，有 \(n\) 个人要互相送礼物。有一个排列 \(p\)，第 \(i\) 个人应该把礼物送给第 \(p_i\) 个人（\(p_i \ne i\)）。

有 \(k\) 个人是拖拉机，她们会忘记带礼物，但是我们不知道这些人是谁。一个人能收到礼物，当且仅当她带了礼物，并且应该送给她礼物的人也带了礼物。

给定 \(p, k\)，对于所有 \(k\) 个人没带礼物的情况，求最少、最多有多少人不能收到礼物。

\(2\le n\le 1\times 10^6,0\le k\le n\)

题解

  • 先考虑收不到的人数最多怎么做。我们将 \(p[i]\) 视作是 \(i\) 集合向外映射的一个集合,相应的我们把它们连上边就组成了一个个的环,我们发现,对于一个大小为 \(s\) 的环只要有 \(\frac{s+1}{2}\) 个人,环内所有人都不会得到礼物了,因此给每个环都这样贪心地做即可
  • 然后考虑收不到的人数最少怎么做。一个显然的贪心是,我们要选一个环就一定要把它选完,因此这变成了选若干个数使得它们的和为 \(k\),如果我们将大小相同的环放在一起,那么这个问题就变成了一个多重背包的问题,直接二进制分组做即可

时间复杂度 \(\mathcal{O}(n\log n)\)

树形dp

P3174 [HAOI2009] 毛毛虫 （树的直径变式）

题目

对于一棵 \(N\) \((N \le 3\times 10^5)\) 个点的树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫。

求点数最多的毛毛虫

题解

本题与树的直径的求法非常类似

设 \(f_u\) 表示以 \(u\) 为头的毛毛虫的最大点数

那么转移就是

\[f_u=\max_{v\in \text{son}_u}f_v+1+\max\lbrace0,\text{cnt}_u-1\rbrace\]

其中 \(\text{cnt}_u\) 表示的是 \(u\) 结点的儿子的个数

然后对于每个点取最大值和次大值进行一个拼接,计算答案即可

时间复杂度\(\mathcal O(N)\)

[BZOJ 3743] Kamp （多次dfs多种信息的处理）

题目

一颗树\(n\)个点，\(n-1\)条边，经过每条边都要花费一定的时间，任意两个点都是联通的。有\(K\)个人（分布在K个不同的点）要集中到一个点举行聚会。聚会结束后需要一辆车从举行聚会的这点出发，把这\(K\)个人分别送回去。请你回答，对于\(i=1~n\)，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。\(K\le N\le 5\times 10^5\)\(1\le x,y\le N,1\le z\le10^6\)

题解

我们找出包含那\(k\)个关键点所组成的最小的连通块，通过画图得知

  • 如果举行聚会的位置在联通块内，那么我们发现答案就是这个联通块的边权和乘\(2\)并减去联通块的直径
  • 如果举行聚会的位置在连通块外，那么我们发现答案就时这个\((这个点到联通块的最短距离+连通块的边权和)\times 2-这个点到联通块中点的最远距离\)

因此考虑树形\(dp\)

记

\[\begin{aligned}&ans_i~~~在第i个点举行聚会的最短时间\\&sum~~~关键点生成树的边权之和\\&dis_i~~~点i到生成树的最短距离\\&maxlen_i~~~点i与到最远关键点的距离\\&f_i~~~点i子树中关键点的个数\\&g_i~~~点i子树外关键点的个数\end{aligned}\]

我们可以一次\(dp\)求出\(i\)的子树内关键点的个数，第二次换根\(dp\)求出\(i\)子树外关键点的个数，如果一个点子树内或子树外的关键点的个数为\(0\),那么这个点就不在关键点生成树中

通过三四次\(dp\)，我们可以求出\(dis_i\)

注意，我们如果求出了关键点生成树的直径的两个端点，设根据求直径时的过程，我们知道，对于在生成树上的点，生成树中距离它最远的点一定是其到直径两个端点的最大值

然后 \(ans_i\) 的转移如下

\[ans_i=2\times (sum+dis_i)-maxlen_i\]

所以总计四次(或三次)\(dp\)便可以转移出答案

P1131 [ZJOI2007] 时态同步 （普通树形dp）

题目

题解

\(sb\)题一道

由于时间只加不减，对于一个点\(i\),求出它子树中的最大时间和原总时间，那么答案的新贡献就是\(最大时间\times siz[i]-原总时间\)

BZOJ 4033 树上染色 （树形背包）

题目

有一棵点数为\(N\)的树，树边有边权。给你一个在\([0,N]\)之内的正整数\(K\)，你要在这棵树中选择\(K\)个点，将其染成黑色，并将其他的\(N-K\)个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。\(N\le 2000,0\le K\le N\)

题解

经典题，树形背包\(dp\)

设\(f[i][j]\)表示子树\(i\)中选了\(j\)个黑点时的全局最大距离，同时维护下子树大小\(siz[i]\)

考虑转移，我们发现，对于一个结点\(i\)，转移时的答案就是\(子树内距离+跨子树距离\)

我们对于一个子树\(v\)，枚举一个\(l\)表示子树中染了\(l\)个黑点，那么子树内的距离就是\(f[v][l]\)

那么子树外的点如何计算呢？我们不妨考虑一个经典套路，考虑每一条边的贡献

对于一条边\(e\),它被经过的次数就是两边同色点个数乘积的和，贡献就再乘上边权就可以了

所以转移就可以这么写

\[f[u][i]=\max_{v\in son(u)}\lbrace f[v][l]+cnt_{black}+cnt_{white}\rbrace\\cnt_{black}=l\times(k-l)\\cnt_{white}=(siz[u]-l)\times(n-k-siz[u]+l)\]

感性理解是每一对点都只会在它们的 \(\text{lca}\) 处被合并一次,所以均摊后时间复杂度是 \(\mathcal O(n^2)\)

严格证明需要势能分析,不展开了

[hdu 6854] Kcats （笛卡尔树dp）

题目

定义维护单调栈的过程为：每次将栈头大于当前数的数弹栈，直到不能弹为止，然后加入当前数。给一个长度为\(n\)的数组\(a\)，问有多少个排列\(p\)满足，将\(p\)的前\(i\)个数依次加入单调栈后，得到栈的大小为\(a_i\)。若\(a_i=−1\)表示 \(a_i\)可以等于任意值。\(n\le 100\)

题解

我们考虑如果没有\(-1\)这道题应该怎么做

考虑笛卡尔树的构建过程，我们每次选择当前区间\([l,r]\)的最小值的位置\(p\)(对应到原题就是从左到右找到最后一个\(a[i]=1\)的位置)，我们发现最小值将整个区间分成了完全不相干的两个部分\([l,p-1], [p,r]\)

我们向左右两边填数，这就是一个组合数问题，显然有

\[ans_{[l,r]}=ans_{[l,p-1]}\times ans_{[p,r]}\times \binom{r-l}{p-l}\]

然后我们考虑加上\(-1\)应该怎么做

设\(f[i][j][k]\)表示，考虑到区间\([i,j]\),当前区间初始栈的大小为\(k\),也就是当前区间笛卡尔树根的深度为\(k\)时的方案数。

那么我们枚举这个区间的笛卡尔树根\(p\),如果\(a_p\)有值则\(k\)只能取\(a_p\)，否则就将当前点改成\(k\)进行转移，转移方程如下

\[\begin{aligned}f[i][j][k]=\sum_{i\le p\le j}f[i][p][k]\times f[p+1][j][k+1]\times \binom{r-l}{p-l}\end{aligned}\]

所以合着这实际是道区间\(dp\)

[CEOI2007] 树的匹配 Treasury （树上父子关系的讨论）

题目

给一棵 \(N\) 个点的树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配

\(N\le 3\times 10^5\)

题解

设 \(f[i][0/1]\) 表示 \(i\) 不与其父亲匹配/与其父亲匹配时的最大匹配; \(g[i][0/1]\) 表示不与其父亲匹配/与其父亲匹配时的最大匹配方案数

其中 \(f[i][1]\) 与 \(g[i][1]\) 是好求的,有

\[f[i][1]=\sum_{j\in \text{son}_i}f[j][0]+1\\ g[i][1]=\prod_{j\in \text{son}_i} g[j][0]\]

剩下两个麻烦一些,令 \(\text{sum}=\sum_{k\in\text{son}_i} f[k][0]\) 则

\[f[i][0]=\max_{j\in \text{son}_u}\lbrace \text{sum}-f[j][0]+f[j][1]\rbrace\\ g[i][1]=\sum_{\text{满足}f[j][0/1]\text{是最大匹配}的 j}\frac{\text{sum}\times g[j][1]}{g[j][0]}\]

时间复杂度 \(\mathcal O(N)\)

关于匹配的另一个小trick

最大匹配唯一其实等价于图中的一个点要么孤立，要么属于最大匹配

P4630 [APIO2018] 铁人两项 （圆方树上dp）

题目

题解

考虑到当我们固定\(s,f\)时，我们\(c\)的选择就是\(s\)到\(f\)所有简单路径的并，然后减去\(2\)(因为\(c\)不可以选在\(s,f\)处)

进一步考虑，\(s\)到\(f\)简单路径的并就是路径上点双大小的并

所以建出原图的圆方树，将方点的权值设为这个点双中圆点的个数，将圆点的权值设为\(-1\)，那么从\(s\)到\(f\)简单路径的并就是圆方树上\(s\)到\(f\)的路径

我们设\(f_i\)表示\(s,f\)在\(i\)子树中的方案数，考虑枚举中转点\(c\)，分两种情况转移

  • 点\(c\)是圆点时，假设它有\(4\)棵子树，它的子树对答案的贡献是
\[S_1S_2+S_1S_3+S_1S_4+S_2S_3+S_2S_4+S_3S_4\]

看上去这个转移是\(\mathcal O(n^2)\)的,是我们可以这么做

\[S_1S_2+(S_1+S_2)S_3+(S_1+S_2+S_3)S_4\]

所以我们每次记一个前缀子树和，然后乘上下一个子树的大小进行转移，这是\(\mathcal O(n)\)的

  • 当\(c\)是方点，如果\(s,f\)不在这个点双内，那么其贡献一定被这个点双中的圆点中就已经统计过了，所以考虑如何计算\(s,f\)在点双内的方案数
  1. 如果\(s,f\)中只有一个在点双中，那么\(c\)可以选的位置就有\(deg-1\)个，总共有\(deg\times (deg-1)\)次贡献，但是当\(f\)选在了割点处，那么\(c\)就无处可选了，乘的另外一部分是相同的，所以整个就少选了\(deg\)次，所以总次数就变成了\(deg\times (deg-2)\)
  2. 如果\(s,f\)都在点双内部，显然可以选择的位置就有\(deg-2\)个

所以在上面圆点的转移乘上\(deg-2\)的系数就行了

HDU 5593 ZYB"s Tree （换根dp）

题目

给定一个 \(n\) 个点的树,每条边的边权是 \(1\)

对于每个点,求出离这个点距离不超过 \(k\) 的点的个数

\(n \le 5\times 10^5,k\le 10\)

题解

所谓换根dp,就是先一遍 \(\text{dfs}\) 求出子树内的信息,再一次 \(\text{dfs}\) 通过求出的子树内信息去递推子树外的信息

对于这一道题,首先,一个点的答案显然可以分为子树内的点和子树外的点,于是我们设 \(f[u][d]\) 表示 \(u\) 子树内距离 \(u\) 为 \(d\) 的点的个数, \(g[u][d]\) 表示 \(u\) 的子树外距离 \(u\) 为 \(d\) 的点的个数

对于 \(f[u][d]\) ,我们可以在向上的时候转移:

\[f[u][d]=\sum_{v\in \text{son}_u}f[v][d-1]\]

对于 \(g[u][d]\) ,我们可以在向下的时候转移:

\[g[u][d]=g[\text{fa}][d-1]+f[\text{fa}][d-1]-f[u][d-2]\]

因为 \(u\) 点的子树外相当于 \(\text{fa}\) 点的子树外加上 \(\text{fa}\) 点的子树内除了 \(u\) 以外的儿子的答案

答案直接将同一个点的 \(f,g\) 相加去取即可,时间复杂度 \(\mathcal{O}(nk)\)

P4381 [IOI2008] Island （基环树dp+单调队列优化dp）

题目

给定一个 \(n\) 个点 \(n\) 条边的基环树森林,边有边权,求每棵基环树的直径长度之和

题解

对于这种基环树的题,先将环和树分开考虑

对于每一棵基环树上的树求出它的直径,并求出它上面的点到环的最远距离为,记它于环的那个公共点为 \(i\) ,记这个最远距离为 \(d[i]\),记环上两点 \(x,y\) 的之间的最长距离为 \(\text{dist}[x][y]\),那我们就是要在环上求出 \(\max\lbrace d[x]+d[y]+\text{dist}[x][y]\rbrace\) 我们先破环成连,然后对于这种转移区间长度固定的dp,考虑使用单调队列优化即可。然后再与各个子树的直径取最大值就是答案

HDU 3586 Information Disturbing （二分+树形dp）

题目

给定一个 \(n\) 个点树,边有边权

现在要求切除其中的一些边,使得叶节点与根节点是不连通的

要求切除的总边权不可以超过 \(m\) ,求所有的切除方案中最大边权的最小值

\(n\le 1000 m\le 10^6\)

题解

首先看到最大值最小,而且答案看上去是关于最小总花费单调的,所以我们考虑进行一个二分

二分一个值为 \(\text{mx}\) ,那么我们要求在dp的过程中不可以切除大小超过 \(\text{mx}\) 的边,设 \(f[u]\) 表示 \(u\) 与它的儿子都断开的最小花费

那么对于边 \((u,v)\) 显然有两种转移

  • 断开边 \((u,v)\) 花费 \(w(u,v)\) ,即 \(f[u]\leftarrow f[u]+w(u,v)\)
  • 在 \(v\) 中就把所有叶子断开了,即 \(f[u]\leftarrow f[u]+f[v]\)

大小超过 \(\text{mx}\) 的就把它特判掉就行,时间复杂度 \(\mathcal O(n\log V)\) ,其中 \(V\) 是边权的值域大小

CF 960E Alternating Tree （拆贡献经典套路）

题目

给定一棵带点权的树，求所有有向路径的权值和。

一条有向路径的权值如下定义：

设这条路径依次经过的点的权值分别为 \(V_1, V_2, ..., V_m\)。

则路径的权值为 \(\sum_{i=1}^m(-1)^{i+1}V_i\)

\(n\le 2\times 10^5\)

题解

首先,偶数长度的路径对答案是没有任何贡献的,因为这条路径的反向路径一定存在且会抵消掉这条路径的贡献

然后直接计算是困难的,所以考虑计算每个点对答案的贡献,也就是要求出每个点作为路径上的偶数位置和奇数位置多少次,设 \(f[u][0/1]\) 表示 \(u\) 子树内的点距离 \(u\) 为偶数/奇数的点构成的路径对答案的贡献,转移是平凡的

设 \(g[u][0/1]\) 表示距离 \(u\) 为偶数/奇数的点构成的路径对答案的贡献,初始状态为 \(g[1][0/1]=f[1][0/1]\) ,转移就是 \(g[u][0/1]=g[\text{fa}][1/0]\) ,由这个转移,我们可以知道当 \(u\) 的深度是奇数时,\(g[u][0/1]=f[1][0/1]\) ,当 \(u\) 的深度是偶数时,\(g[u][0/1]=f[u][1/0]\) ,这样我们就可以求出由 \(u\) 子树外的点到 \(u\) 的长度为偶数/奇数的贡献次数,于是我们就可以采用和 "P4630 [APIO2018] 铁人两项" 相似的转移方法去计算答案即可

时间复杂度 \(\mathcal O(n)\)

POJ 2486 Apple Tree （树上路径问题1）

题目

给定一棵 \(n\) 个点的树,每个点上有一个权值，求从 \(1\) 出发，走 \(m\) 步，最多能遍历到的权值

\(n\le 100,m\le 200\)

题解

设 \(f[u][d][0/1]\) 表示没有端点/一个端点在 \(u\) 的子树内(回到 \(u\) ),走 \(d\) 步时能遍历到的最多的权值是多少

转移分三种情况转移,注意边 \((u,v)\) 被经过的次数

  • 从 \(u\) 到其子树中再回到 \(u\)
\[f[u][d+2][0]=\max_{v\in \text{son}_u}\lbrace f[u][d-k][0]+f[v][k][0]\rbrace\]
  • 从\(v\) 返回到 \(u\) ,再到其子树
\[f[u][d+2][1]=\max_{v\in \text{son}_u}\lbrace f[v][k][0]+f[u][d-k][1]\rbrace\]
  • 直接从 \(u\) 到其子树
\[f[u][d+1][1]=\max_{v\in \text{son}_u}\lbrace f[u][d-k][0]+f[v][k][1]\rbrace\]

转移即可

P7163 [COCI2020-2021#2] Svjetlo （树上路径问题2）

题目

题解

难以使用语言描述的题,与 "POJ 2486 Apple Tree" 不同的是这道题没有规定起点,所以本题关键思路在于设 \(f,g,h\) 分别表示路径断端点不在子树内/有一个端点在子树内/两个端点都在子树内,然后分情况讨论,具体转移方程见代码

#include#define int long longusing namespace std;const int N=1e6+10,inf=0x3f;inline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=="-") f=-1;for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);return x*f;}int n,rt,f[N][2],g[N][2],h[N][2];//表示走完子树之后，u是1开还是0关 //f是两头出,g是一头出,h是两头都在子树内string c;int cnt,head[N];struct Edge{int v,nxt;}edge[N<<1];inline void add_edge(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt;}bool ok[N];inline void init(int u,int fa){if(c[u-1]=="1") ok[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==fa) continue;init(v,u);ok[u]&=ok[v];}return;}inline int Min(int x,int y,int z){return min(x,min(y,z));}inline void dfs(int u,int fa){f[u][c[u-1]-"0"]=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==fa||ok[v]) continue;dfs(v,u);int f0=f[u][0],f1=f[u][1],g0=g[u][0],g1=g[u][1],h0=h[u][0],h1=h[u][1];//u,v均开灯 u,v均关灯 f[u][1]=min(f0+f[v][0]+2,f1+f[v][1]+4);//u关v开 u开v关 f[u][0]=min(f1+f[v][0]+2,f0+f[v][1]+4);//u,v均开灯 u,v均关灯g[u][1]=min(g0+f[v][0]+2,Min(g1+f[v][1]+4,f0+g[v][1]+1,f1+g[v][0]+3));//u开v关 u关v开g[u][0]=min(g1+f[v][0]+2,Min(g0+f[v][1]+4,f1+g[v][1]+1,f0+g[v][0]+3)); //u,v均开灯 u,v均关灯 h[u][1]=Min(min(f0+h[v][0]+2,f1+h[v][1]+4),min(g0+g[v][0]+2,g1+g[v][1]),min(h0+f[v][0]+2,h1+f[v][1]+4));//u关v开 u开v关 h[u][0]=Min(min(f1+h[v][0]+2,f0+h[v][1]+4),min(g1+g[v][0]+2,g0+g[v][1]),min(h1+f[v][0]+2,h0+f[v][1]+4));}//当x为根时 g[u][0]=min(g[u][0],f[u][1]+1);g[u][1]=min(g[u][1],f[u][0]+1);h[u][0]=min(h[u][0],g[u][0]);h[u][1]=min(h[u][1],g[u][1]);//cout<>c;for(int i=1;i

状态压缩DP

相关技巧

  • 枚举子集：如果一个集合状态 \(S\) 由其所有子集 \(S0\subsetneq S\) 转移得到，这样转移的时间复杂度为 \(\sum\limits_{i = 0} ^ n\dbinom n i 2 ^ i=3 ^ n\)
for(int S0 = S; S0; S0 = (S0 - 1) & S) {{...}
  • 高维前缀和

考虑二维前缀和还可以怎么计算：对于每一维，枚举剩下所有维的所有可能，计算关于该维的前缀和。

高维前缀和就是这样的原理。通常情况下每个维度大小为 \(2\)，维数为 \(n\)：枚举每一维 \(d\)，然后枚举所有状态（用二进制数来表示），如果当前状态 \(i\) 的第 \(d\) 位为 \(1\)，就加上 \(i-2^d\) 那个状态的值。

for(int d=0;d>d)&1)f[i]+=f[i^(1<

时间复杂度 \(\mathcal O(n2^n)\)

HDU 4628 Pieces （子序列状压的一般套路）

题目

给定一个长度为 \(n\) 的字符串,一次操作定义为选出一个回文子序列并删掉,问将整个字符串删完的最少的操作次数

\(n\le 16\)

题解

设 \(f[s]\) 表示将序列 \(s\) 完全删除的最小的操作次数,对于所有 \(s\) 为回文串的 \(f[s]=1\) ,转移就是枚举子集转移 \(f[s]=\min_{x\subseteq s} f[x]+f[s^x]\),其中 \(x\) 是回文串,时间复杂度 \(\mathcal O(3^n)\)

HDU 6149 Valley Number II （图上状压一般思路）

题目

给定一个 \(n\) 个点 \(m\) 条边的无向图,其中 \(k\) 个点被标记为高点,\(n-k\) 个点被标记为低点

一个山谷定义为一个三元组 \(\) ,满足 \(x,z\) 是高点, \(y\) 是低点,而且 \(x,y\) 和 \(y,z\) 之间均有边相连

如果一个点只能在一个山谷中,求这张图最多有多少个山谷

\(x\le 30,k\le \min(n,15)\)

题解

首先,注意到 \(k\) 的范围是很小的,所以我们考虑将高点的使用情况进行状压

设 \(f[i][s]\) 表示考虑到第 \(i\) 个低点,使用了集合 \(s\) 中的高点,所能够形成的山谷有多少个

假设我们考虑到第 \(i\) 个点,要向 \(i+1\) 进行转移,那么就在图中找到所有与 \(i+1\) 相连的高点,然后转移即可

P3959 [NOIP2017 提高组] 宝藏 （分层法确定DP顺序）

题目

给定一个 \(n\) 个点 \(m\) 条边的无向图,边有边权。找到这张图的一棵生成树,记一个点到根距离为 \(\text{L}\) ,点的个数为 \(\text{K}\) ,这个点的贡献为 \(\text{L}\times \text{K}\) ,要求最小化贡献和

题解

考虑根据离根的深度(从当前到根经过的点数),一层一层进行DP

设 \(f[i][s]\) 表示考虑到第 \(i\) 层,选了 \(s\) 集合中的点的最小贡献

转移为

\[f[i][s]=\min\lbrace f[i-1][s_0]+\text{cost}(s_0,s)\times (i+1) \rbrace\]

其中 \(\text{cost}(s_0,s)\) 表示的是从状态 \(s_0\) 到 \(s\) 的最短距离,可以预处理出来

时间复杂度为 \(\mathcal O(3^nn^2)\)

P6622 [省选联考 2020 A/B 卷] 信号传递 （状态的设计及优化）

题目

题解

按题意，我们暴力枚举这 \(m\) 个信号站的排列顺序，时间复杂度 \(\mathcal O((m!)\cdot n)\) 。

容易发现，题目给出的这个长度为 \(n\) 的序列S具体是什么不重要，重要的是，每一对信号站 \(i,j\) ，在 \(S\) 里作为相邻的位置，出现了多少次。也就是有多少个位置 \(p (1\leq p

对于任意 \(i\neq j\)，\(\text{cnt}[i][j]\) 就表示要从信号站 \(i\) ，向信号站 \(j\)，进行多少次传递。设两个信号站的位置，分别为 \(\text{pos}[i]\),\(\text{pos}[j]\)，则它们会对答案产生的代价就是：

\[\begin{cases}\text{pos}[j]-\text{pos}[i]&&(\text{pos}[i]<\text{pos}[j])\\k\cdot(\text{pos}[i]+\text{pos}[j])&&(\text{pos[i]}>\text{pos}[j])\end{cases}\]

这样我们就干掉了 \(n\) 的限制,时间复杂度为 \(\mathcal O(n+(m!)\cdot m^2)\)

接下来我们有两种状压DP的状态设计

  • 按位置考虑:设 \(f[s]\) 表示考虑完前 \(|s|\) 个数,填了集合 \(s\) 中位置
  • 按值考虑:设 \(f[s]\) 表示考虑完前 \(|s|\) 个位置,填了集合 \(s\) 中的数

这是状压DP中两个极为常见的状态设计,而本题适用于第二种状态设计

为了方便转移,我们将点对的贡献拆解为单点的贡献,具体来说,假设我们考虑到第 \(\text{pos}\) 个位置:

  • 对于一个前面的数 \(j\) ，从 \(i\) 到 \(j\) 产生的代价是：\(\text{pos}\cdot k\cdot \text{cnt}[i][j]\)。
  • 对于一个前面的数 \(j\) ，从 \(j\) 到 \(i\) 产生的代价是：\(\text{pos}\cdot\text{cnt}[j][i]\) 。
  • 对于一个后面的数 \(j\)，从 \(i\) 到 \(j\) 产生的代价是：\(-\text{pos}\cdot \text{cnt}[i][j]\) 。
  • 对于一个后面的数 \(j\)，从 \(j\) 到 \(i\) 产生的代价是：\(\text{pos}\cdot k\cdot \text{cnt}[j][i]\) 。

转移方程就是

\[f[s+i]\leftarrow f[s]+\text{pos}\cdot \sum_{j\in s}(k\cdot\text{cnt}[i][j]+\text{cnt}[j][i])+\text{pos}\cdot\sum_{j\notin(s+i)}(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i])\]

如果枚举 \(i\) ，再枚举 \(j\)，DP的时间复杂度 \(\mathcal O(2^mm^2)\)

我们继续优化。考虑只枚举 \(i\)。把 \(\text{pos}\)前的系数（也就是所有 \(j\) 的贡献之和），预处理出来，不妨记为：\(\text{cost}(s,i)\)。那么上述的转移式，也可以改写为：

\[f[s+i]\leftarrow f[s]+\text{pos}\cdot \text{cost}(s,i)\]

考虑预处理 \(\text{cost}(s,i)\)。首先，根据定义，\(i\notin s\)。

我们考虑，\(\text{cost}(s,i)\)，可以从“ \(s\) 去掉某个数”的状态，转移过来。我们不妨就去掉 \(j=\text{lowbit}(s)\)。那么，

\[\text{cost}(s,i)=\text{cost}(s-j,i)+(k\cdot \text{cnt}[i][j]+\text{cnt}[j][i])-(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i])\]

这样转移是 \(\mathcal O(1)\) 的。所以预处理的时间复杂度为 \(\mathcal O(2^mm)\)，DP的时间复杂度也降为 \(\mathcal O(2^mm)\)。总时间复杂度 \(\mathcal O(n+2^mm)\)。但是 \(\text{cost}\) 数组会占用 \(\mathcal O(2^mm)\) 的空间，这无法承受。所以还要继续优化空间。

发现 \(\text{cost}\) 和 \(f\) 的转移，都是按集合从小到大进行的。所以我们不妨就按这个顺序，一边DP，一边求 \(\text{cost}\)。

对每个 \(s\)，我们把 \(\text{cost}(s,\dots)\) 视为一个大小为 \(m\) 的数组。当前的 \(s\)，我们先做DP转移，再拿 \(\text{cost}(s\dots)\) 数组去更新所有 \(\text{cost}(s"\dots )\)。发现更新完之后，\(\text{cost}(s,\dots)\) 这个大小为 \(m\) 的数组，就可以删掉

可以采取滚动数组的方式来实现,这样空间复杂度也符合要求了,可以通过本题

P1777 帮助 （普通状压dp）

题目

定义一个长度为 \(n\) 的序列的混乱度为序列中不相等连续段的个数,序列的极差不超过 \(7\) 现在你可以从序列中删掉 \(k\) 个值,求最小的混乱度

\(n,k\le 100\)

题解

首先离散化一下,得到一个新的数组 \(h\),\(h\) 的值域为 \(0\sim 7\)

设 \(f[i][j][k][l]\) 表示考虑到第 \(i\) 个位置,删去了 \(j\) 个数,选的数的集合为 \(k\) ,最后一个没有被删的数为 \(l\) ,那么显然有转移

  • 如果第 \(i\) 个位置没有被删
\[f[i][j][k|(1<
  • 如果第 \(i\) 个位置被删
    • \[f[i][j+1][k][l]=\min\lbrace f[i-1][j][k][l]\rbrace\]

    时间复杂度 \(\mathcal O(mk\times 8\times 2^8)\)

    [BZOJ 1231] mixup2 （普通状压dp）

    题目\(\text{Farmer John}\)的\(N\)头奶牛中的每一头都有一个唯一的编号\(S_i\). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感.如果一个队伍里所有两头相邻的奶牛的编号相差超过\(K\), 它就被称为是混乱的. 比如说，当\(N = 6, K = 1\)时\(1, 3, 5, 2, 6, 4\)就是一支"混乱"的队伍, 但是\(1, 3, 6, 5, 2, 4\)不是(因为\(5\)和\(6\)只相差\(1\)). 那么, 有多少种能够使奶牛排成"混乱"的队伍的方案呢?

    题解

    设 \(f[i][s]\) 表示考虑到第 \(i\) 头奶牛，奶牛的选取情况为 \(s\) 的方案数

    转移时，如果当前枚举的 \(s\) 中不含 \(i\) 那么直接跳过，否则 \(f[i][s]\) 就可以从 \(f[j][s|(1<< (i-1))]\) 转移

    P5933 [清华集训2012]串珠子 （连通图中的状压dp）

    题目

    给定 \(n\) 个点,两个点之间有 \(c[i][j]\) 条本质不同的边,求构成连通图的方案数

    题解

    直接维护连通是是困难的,那么正难则反

    设 \(f[s]\) 表示点集为 \(s\) 且连通的方案数, \(g[s]\) 表示点集为 \(s\) 时任意连边的方案数, \(h[s]\) 表示点集为 \(s\) 时不连通的方案数

    显然\(g[s]=\prod_{i,j\in s}(c[i][j]+1)\)

    关于 \(h[s]\) ,可以任取 \(s\) 中的一个点 \(p\),设与 \(p\) 连通的子集为 \(s_1\) ,与 \(p\) 不连通的子集为 \(s_2\),那么 \(h[s]=f[s_1]\times g[s_2]\)

    有\(f[s]=g[s]-h[s]\)

    于是我们枚举子集转移即可

    P2704 [NOI2001] 炮兵阵地 （多行影响的状压dp）

    题目

    在 \(N \times M\) ( \(N \le 100\) , \(M \le 10\) ) 的网格地图上部署炮兵部队。每一格可能是山地或平原，一个炮兵部队的攻击范围是长宽为 \(5\) 的十字形，炮兵部队只能部署在平原。

    求在炮兵部队之间不能互相攻击的前提下，最多能部署多少炮兵部队。

    题解

    考虑到

    • 列数很小，可以状压。
    • 每个炮兵可以向上影响两行，状压一行是不够的。
    • 每个炮兵会向左右影响两个，每列放炮兵的方案不多。

    于是我们可以状压两行,设 \(f[i][A][B]\),表示考虑到第 \(i\) 行,第 \(i-1\) 行的状态为 \(A\),第 \(i-2\) 行的状态为 \(B\) 的方案数

    直接转移就行

    CF453B Little Pony and Harmony Chest （根据题目性质减少压缩状态的大小）

    题目

    给定长为 \(n\) 的数组 \(a[]\)，要构造长为 \(n\) 的正数数组 \(b[]\)，要求 \(b[]\) 中的数两两互质，且最小化

    \[val=\sum_{i=1}^n|a_i-b_i| \]

    输出 \(b[]\) 。

    \(1\le n \le 100, 1\le a_i\le 30\)

    题解

    若存在某 \(b_i\ge 59\)，那就不如把 \(b_i\) 改成 \(1\) ，因为 \(b_i-a_i\ge a_i-1\)，且改成\(1\)不影响互质。

    所以 \(1\le b_i< 59\)。所有 \(b_i\) 的质因子分解式中，出现的质数只可能为 \(2,3,5,7,\cdots,53\)，共\(16\)个。

    用状态 \(s\) 记录选了哪些质数。\(f(i,s)\) 表示考虑 \(a[1\sim i]\)，已经用过的质数集为 \(s\) 的最小 \(val\) 值。

    枚举上一个的状态 \(s\)，再从 \(1\) 到 \(58\) 枚举现在要用哪个数，更新状态。记录 \(s\) 用于回溯

    互质 （状压dp与背包的结合）

    题目

    有 \(n\) 个数，问这 \(n\) 个数里最多选出几个数，使得选出的数两两之间互质。

    \(1\le n\le 1000\)\(1\le 数字\le 1000\)

    题解\(33\)以内的质因数只有\(12\)个一个\(1000\)以内的数，超过\(33\)的质因数只可能有一个

    记一个状态\(s\)表示那\(12\)个质数的选择情况

    • 对于任意一个数,只有\(33\)以内的质因数：这样的话，直接暴力转移即可

    • 有\(33\)以上的质因数：将拥有相同的、大于\(33\)的质因数的数存成一组，分组背包转移

    \(f[i][s]\)表示前\(i\)个数当中，选出了一些互质的数他们含有\(s\)里这些质因数的情况下，最多能选出的数的个数

    复杂度\(\mathcal O(n2^{12})\)

    BZOJ 5180 Cities （最小斯坦纳树）

    题目

    给定\(n\)个点，\(m\)条双向边的图。其中有\(k\)个点是重要的。每条边都有一定的长度。现在要你选定一些边来构成一个图，要使得\(k\)个重要的点相互连通，求边的长度和的最小值。

    \(k\le 5\)

    \(n\le 10^5\)

    \(1\le m\le 2\times 10^5\)

    题解

    首先，答案子图一定是一棵树，因为如果有环，那么一定可以断掉一条边使答案更优且保持图的联通

    那么我们设\(f[i][s]\)表示以\(i\)为根，选了\(s\)中的点的最优答案

    • 当点\(i\)度数为\(1\),设与它联通的点是\(j\),那么有转移
    \[f[i][s]\leftarrow w_{i,j}+f[j][s]\]
    • 当点\(i\)的度数大于\(1\)时，我们考虑枚举\(T\subseteq S\),那么有转移
    \[f[i][s]\leftarrow f[i][S-T]+f[i][T]\]

    上面那个转移很像最短路算法的三角不等式，使用\(dijkstra\)或\(spfa\)进行松弛操作转移\(\mathcal O(m\log m 2^k)\)

    下面那个转移可以采取枚举子集的方法进行转移\(\mathcal O(n3^k)\)

    与\(i\)联通的点每次转移都只会多一个，类似于背包，我们可以\(S\)从小到大枚举

    每次松弛操作从\(j\)扩展到\(i\)时，如果\(i\)时关键点，没有算上\(i\)怎么办呢？不用管，因为后面一定有一次枚举子集转移时会把\(i\)算上

    所以这个转移是正确，使用\(dij\)时间复杂度\(\mathcal O(m\log m 2^k+n3^k)\),不过这题的复杂度瓶颈并不在使用\(SPFA\)，因此使用\(SPFA\)会更快

    [ATC 2230] Water Distribution （状压与最小生成树）

    题目

    在一个二维平面上有N个城市， 第\(i\)个城市的坐标是\((x_i,y_i)\)， 一开始拥有的水量是\(a_i\)。现在你可以从一个城市向另一个城市运送任意数量的水， 但水在运输过程中会有损耗， 具体而言如果从\(x\)城市运\(L\)水到\(y\)城市，最终\(y\)城市得到的水量是\(\max(0,L−dis(x,y))\)， 其中\(dis(x,y)\)指\(x\)和\(y\)城市间的欧几里得距离。 你可以多次进行这个操作。你要使最终水量最少的城市水量尽量多， 求这个值，精度误差不超过 \(10^{-9}\).

    \(1\le N\le 15\)

    题解

    枚举所有\(2^{15}\)次方种子集，对每一种子集求最小生成树检查一下是否能够送水，并求出最小的水量，记此时状态为\(f[s]\),\(s\)是此时点的选取情况，表示这个联通块的最小值为多少，时间复杂度\(\mathcal O(2^nn^2\log n)\)

    然后对整个点集枚举子集的子集进行合并转移，时间复杂度是\(\mathcal O(3^n)\)的

    总时间复杂度是\(\mathcal O(2^nn^2\log n+3^n)\)

    [AGC 012E] Camel and Oases （根据题目性质巧妙选取压缩状态）

    题目

    数轴上有\(n\)个点，初始\(V=V_0\)，每次可以从一个点走到与他距离不超过\(V\)的点。当\(V>0\)时也可以让\(V=V/2\)并瞬移到任意一个点。对于\(i=1\cdots n\)问从\(i\)号点出发能否遍历所有点。

    \(1\le n,V_0\le 2×10^5\)

    题解

    首先\(V\)的取值只能有\(\log V_0\)种，对于每一种\(V\)的取值，它能够走的是一段段的连续的线段。所以我们可以考虑将图分成\(log V_0\)层连续的线段。

    考虑一下用什么样的方式统计答案，我们可以考虑枚举第一层的每条线段\((l_i,r_i)\)，如果说存在一种方案使得从\(1\)开始覆盖到一个\(\ge li−1\)的位置，从\(n\)开始覆盖到一个\(\le r_i+1\)的位置，那么这段线段中的每一个点都是\(Possible\)的，否则就是\(Impossible\)

    此时那个分层线段有一个性质：对于不同层之间的线段，它们相互之间要么上面的完全包含下面的，要么完全不相交

    所以这时我们可以考虑维护\(lp[s],rp[s]\)分别表示从\(1\)开始向右可以扩展到的最右端和从\(n\)开始向左的最左端

    通过状压每一层是否被选过，我们向中间选取连续的线段。假设我们现在要放第\(i\)层的线段，那么我们就要找到上一个状态扩展最远的位置，然后进行转移

    \(st(i)\)表示当前我们选的那一层,定义两个过程：\(mr(i,x)\)表示在第i层的线段中，严格大于x的第一个右端点，\(ml(i,x)\)表示在第\(i\)层的线段中，严格小于x的最靠近\(n\)的右端点

    那么转移如下

    \[lp[st|St(i)]=\max \lbrace lp[st|St(i)],ml(i,lp[st])\rbrace\\rp[st|St(i)]=\min\lbrace rp[st|St(i)],mr(i,rp[st]−1)\rbrace\]

    处理完这个，如上文所言，我们就直接暴力枚举第一层的线段，然后\(check\)就可以了

    [SRM 713] DFSCount （树上状压）

    题目

    给定一个\(n\)个点的简单无向图，问\(DFS\)序总共可能有多少种不同情况?

    \(N\le 14\)题解

    设 \(f[i][s]\) ,表示以 \(i\) 为起点，走了 \(s\) 中点所产生的 \(\text{dfs}\) 序的个数

    考虑 \(\text{dfs}\) 的过程，这显然是一棵树，并且只有把一棵子树中所有的点全部走完之后才会回溯到原来的点

    那么对于状态 \(f[i][s]\) 的转移，我们可以使用并查集维护所有的连通块，当前点\(i\)可以转移到去掉\(i\)之后的所有连通块中，由于转移顺序比较神奇，所以我们直接记搜即可

    CF1342F Make It Ascending （交换状态与值域）

    题目

    给定一个长度为 \(n\) 的序列 \(a\)，每次可以两个位置 \(i,j(i\neq j)\)，令 \(a_j\) 等于 \(a_i+a_j\) 并将 \(a_i\) 从序列中删除。

    求将原序列变成严格单调上升的最少操作次数。

    \(n\leq 15\)

    题解

    先将每个集合及其元素和预处理出来

    设 \(f[i][p][s]\) 表示考虑了前 \(i\) 个集合,第 \(i\) 个集合剩下的那个元素位置是 \(p\),已经使用的数组成的集合是 \(s\) 时的最小操作次数

    转移时枚举集合 \(s\) 的补集，并入第 \(i\) 个集合或者新建第 \(i+1\) 个集合。保证新加入的第 \(i+1\) 个集合中元素和大于第 \(i\) 个集合且有在 \(p\) 之后的元素。时间复杂度为 \(\mathcal{O}(n^23^n)\)

    这道题涉及到方案的输出,因此给一个代码

    #includeusing namespace std;inline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=="-") f=-1;for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);return x*f;}const int N=16,inf=0x3f3f3f3f;int T,n,a[N],f[N][N][1<f[i][p][s]&&(s0>>p)!=0)//s0的数的和大于上一个集合,并且有在p之后的数 {node v=(node){i+1,p+1+__builtin_ctz(s0>>p),s|s0};update(u,v,sum[s0]);//记录dp路径,方便输出答案 }}}node ans=(node){-1,-1,-1};for(int i=n;i>=1;--i){for(int p=1;p<=n;++p)if(f[i][p][(1<

    P2150 [NOI2015] 寿司晚宴 （根据质因子缩减范围）

    题目

    题解

    我们进行根号分治

    \(n\le 500\) 时，考虑小于 \(\sqrt{n}\) 的就那 \(8\) 个,而大于 \(\sqrt{n}\) 的质因子最多就只能有一个,所以我们可以先用状压求出小于 \(\sqrt{n}\) 的那一部分质因子,然后枚举大于 \(\sqrt{n}\) 的质因子就可以了

    具体来说,设 \(f[s_1][s_2]\) 表示两个人选的质因子集合分别为 \(s_1,s_2\) 时且让第一个人选大质因子的方案数,相应的 ,\(g[s_1][s_2]\) 表示让第二个人选大质因子的方案数,\(\text{dp}[i][j]\) 表示的是总方案数,显然有如下转移

    \[\begin{cases}f[s_1|k][s_2]+=f[s_1][s_2]~~~(s_2\And k=0)\\ g[s_1][s_2|k]+=g[s_1][s_2]~~~(s_1\And k=0)\end{cases}\\\text{dp}[s_1][s_2]=f[s_1][s_2]+g[s_1][s_2]-\text{dp}[s_1][s_2]\]

    后面需要减去一个 \(\text{dp}[s_1][s_2]\) 是因为两者都不选的情况被统计了两次

    时间复杂度 \(\mathcal{O}(n2^{16})\)

    NOIP 四校联测 Day3 数字重组 （对极差的处理方法+增加维数）

    题目

    给一个长度为 \(n\) 的序列 \(a\),我们现在要将这 \(n\) 个数等分成 \(k\) 个集合,每个集合有 \(\frac{n}{k}\) 个元素 \((n~\text{mod}~k=0)\) ,每个集合中不能有重复的数,要求最大化集合中元素的极差之和

    \(n\le 70\)

    题解

    数据范围很小,又是个跟集合划分有关的问题,明显是个状压dp

    先来考虑怎么处理极差。

    众所周知极差 \(=\max-\min\) ,所以我们从小到大考虑每个 \(a[i]\) ,将其放入每一个集合中。假设当前考虑到一个集合,我们要把一个数 \(x\) 放进去,当这个集合中为空时,就是对 \(\min\) 有了 \(x\) 的贡献,总极差 \(-x\) ;当这个集合只差一个就满时,就是对 \(\max\) 有 \(x\) 的贡献,总极差 \(+x\)

    于是我们设 \(f[i][s]\) 表示考虑到第 \(i\) 个元素,集合的选取状况是 \(s\) ,注这个 \(s\) 可以使用 \(\text{vector}\) 存,由于我们存元素的集合本质相同,所以可以将 \(s\) 中的数量从小到大排序,方便转移

    注意到题目中要求我们保证各个集合中没有重复元素,所以我们要增一维 \(j\) ,表示上一次放在了哪个位置(代码中表示的是上一次加入 \(a[i-1]\) 的那个集合中数的个数)。

    然后特判+转移即可,详见代码

    本题的复杂度证明是难点,注意到每个状态都能看作从 \((0, 0)\) 出发往右往上走到达 \((k,\frac{n}{k})\)的折线,由此可知状态数为 \(\binom{k+\frac{n}{k}}{k}\le \binom{2\sqrt n}{\sqrt n}\)

    所以总的时间复杂度是 \(\mathcal{O}\left(nk \binom{2\sqrt{n}}{\sqrt{n}}\right)\)

    代码如下:

    #includeusing namespace std;#define int long longinline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=="-") f=-1;for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);return x*f;}const int N=110,M=60010,inf=1e18;vector S[M];map,int> mp;int n,k,tmp[N],cnt,sum[M],a[N];int f[2][M][N];inline void init(int x){if(x>k){++cnt;for(int i=1;i<=k;++i)S[cnt].push_back(tmp[i]),sum[cnt]+=tmp[i];mp[S[cnt]]=cnt;return;}for(int i=tmp[x-1];i<=n/k;++i){tmp[x]=i;init(x+1);}}signed main(){freopen("num.in","r",stdin);freopen("num.out","w",stdout);n=read();k=read();for(int i=1;i<=n;++i) a[i]=read();sort(a+1,a+1+n);init(1);//预处理选择的状态 memset(f,inf,sizeof(f));f[0][1][0]=0;for(int i=1;i<=n;++i){for(int s=1;s<=cnt;++s){if(sum[s]!=i) continue;for(int j=0;j<=n/k;++j)f[i&1][s][j]=inf;}for(int s=1;s<=cnt;++s)//s-->x {if(sum[s]!=i-1) continue;for(int j=0;j<=n/k;++j){for(int p=0;p nw=S[s];++nw[p];//当前位置新增一员 if(a[i]==a[i-1]){if(S[s][p]>j) continue;int x=mp[nw];//对应的状态编号int val=0;if(S[s][p]==n/k-1) val+=a[i];//最大的 if(S[s][p]==0) val-=a[i];//最小的 f[i&1][x][S[s][p]]=min(f[i&1][x][S[s][p]],f[(i&1)^1][s][j]+val);}else{int x=mp[nw];int val=0;if(S[s][p]==n/k-1) val+=a[i];if(S[s][p]==0) val-=a[i];f[i&1][x][S[s][p]]=min(f[i&1][x][S[s][p]],f[(i&1)^1][s][j]+val);}}}}}printf("%lld\n",f[n&1][cnt][n/k-1]);return 0;}

    期望DP

    关键：期望的线性性

    即\(E(x+y)=E(x)+E(y)\)

    期望的其它性质(\(C\)是常数)

    \[E(C)=c\\ E(Cx)=CE(x)\\ \text{当X与Y互相独立},E(xy)=E(x)E(y)\]

    路径长度 （倒推与期望的线性性）

    题目

    给定一个起点为\(1\),终点为\(n\)的\(DAG\),每个点走向与他相连的点的概率是相等的，求从\(1\)到\(n\)的路径的期望总长度

    题解

    1. 方法\(1\)：倒序\(dp\)，适用于终点唯一的情况

      我们设\(f[i]\)表示从\(i\)到终点\(n\)的方案数，根据拓扑序的逆序转移，转移方程为

    \[f[u]=\sum_{v\in \text{connect}(u)}\frac{f[v]+w}{\deg v}\]

    1. 方法\(2\)：利用期望的线性性计算，设\(f[i]\)表示点\(i\)期望被经过的次数，我们只需要计算每一条边被计算的次数即可，如果点\(u\)期望被经过的次数为\(f[u]\)，那么边\((u,v,w)\) 期望被经过的次数就为\(\frac{f[u]}{\deg u}\),对答案的贡献就乘上\(w\)加起来就行了。

      那么我们如何计算\(f[u]\)呢？显然\(f[1]=1\)，接下来我们按拓扑序进行转移\(f[v]\leftarrow \frac{f[u]}{\deg u}\)即可

    乘坐电梯 （利用期望的定义求解）

    题目

    有\(n\)个人排成一列，每秒中队伍最前面的人有\(p\)的概率走上电梯（一旦走上就不会下电梯），或者有\(1−p\)的概率不动。问你\(T\)秒过后，在电梯上的人的期望。

    \(1\le n, t\le 2000,0\le p\le 1\)

    题解

    我们设\(f[i][j]\)表示第\(i\)个时刻电梯上有\(j\)个人的期望

    1. 方法\(1\),我们的结束状态并不一定，因此是没有办法使用上一道题的方法\(1\)的
    2. 方法\(2\),我们将状态之间的转移抽象成边，只有\(f[i][j]\rightarrow f[i+1][j+1]\)的转移对答案有\(1\)的贡献,然后具体转移与上一道题是同理的
    3. 方法\(3\),直接利用期望的定义进行\(dp\)。我们直接将上面状态的期望改为概率，那么就有转移\(f[i+1][j+1]\leftarrow f[i][j]\times p,f[i+1][j]\leftarrow f[i][j]\times (1-p)\)，答案就是\(\sum_{0\le k\le n}f[T][k]\times k\)

    NOIP四校联测 Day1 T1 （多数组优化转移）

    题目

    给定一个整数 \(n\) ,表示开始时手上的数,初始黑板上的数为 \(1\)

    现在进行若干次操作,假设当前手上的数为 \(m\) 每次选择一个 \(i\in [1,m]\) ,让黑板上的数字乘 \(k\) 的同时,让手上的数变为 \(m-i\) ,当这个数变为 \(0\) 的时候停止操作

    求出黑板上的数的最大值和期望大小

    \(n\le 5\times 10^5\)

    题解

    首先这道题不能当成一个整数划分来做,因为每种情况并不是等概率(笔者赛时 \(\text{SB}\) 愣是算了 \(1\) 个小时都没算对样例)

    对于第一问,根据打表,通过观察,如果一个数 \(\le 4\) ,我们将它分成若干个 \(2\) 和 \(3\) 的乘积,结果一定不会变劣。再考虑每有 \(3\) 个 \(2\) ,我们就可以把它换成 \(2\) 个 \(3\) ,一定会变优。因此这一问就根据模 \(3\) 的余数分一下类就行了

    对于第二问,设 \(f[i]\) 表示手上的数是 \(i\) 时,黑板上的数的期望。转移就是

    \[f[i]=\frac{1}{i}\sum_{k=1}^{i}f[i-k]\times k\]

    为了优化这个转移,我们可以设 \(g[i]=\sum_{k=1}^{i}f[k]\) ,设 \(h[i]=\sum_{k=1}^{i}f[k]\times (i-k+1)\)

    于是有

    \[f[i]=\frac{1}{i}\times h[i-1]\\ h[i]=h[i-1]+g[i]\]

    时间复杂度 \(\mathcal{O}(n)\)

    期望收益 （拆分计算非线性期望）

    题目

    给定一个长为\(n\)的序列，一些位置没有被确定（是\(o,x\)的几率各占\(50\%\)）。对于一个\(ox\)序列，连续\(a\)长度的\(o\)会带来\(a^2\)的收益，问最终序列的期望收益是多少

    \(n\le 10^6\)

    题解

    如果我们采取普通的一段一旦处理的方法计算，并不好做，状态数太多。我们观察到\((x+1)^2-x^2=2x+1\),所以设\(f[i]\)表示考虑到第\(i\)位的期望贡献，\(l[i]\)表示以\(i\)结尾的极大连续\(o\)的期望长度,转移如下

    \[\begin{cases}f[i]=f[i-1]+l[i-1]\times 2+1,l[i]=l[i-1]+1~(o)\\f[i]=f[i-1],l[i]=0~(x)\\f[i]=f[i-1]+\frac{l[i-1]\times 2+1}{2},l[i]=\frac{l[i-1]+1}{2}~(?)\end{cases}\]

    时间复杂度\(\mathcal O(n)\)

    P1654 OSU! （拆分计算非线性期望）

    题目

    对于每一个序列，每个位置为\(o\)的概率为\(p_i\),为\(x\)的概率为\(1-p_i\),对于一个\(ox\)序列，连续\(a\)长度的\(o\)回得到\(a^3\)的收益，问最终得到\(ox\)序列的期望收益是多少？

    题解

    同上一题的思路，我们仍然考虑每一个位置的贡献。根据\((x+1)^3-x^3=3x^2+3x+1\),所以我们维护\(l_1[i]\)为最大连续\(o\)期望长度,\(l_2[i]\)为长度的平方。

    线性转移即可

    [HNOI2013]游走 （高斯消元求解图上带环dp）

    题目

    给定一个 \(n\) 个点 \(m\) 条边的无向连通图，顶点从 \(1\) 编号到 \(n\)，边从 \(1\) 编号到 \(m\)。

    小 Z 在该图上进行随机游走，初始时小 Z 在 \(1\) 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 \(n\) 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 \(m\) 条边进行编号，使得小 Z 获得的总分的期望值最小

    题解

    我们考虑一个贪心，期望经过次数最多的边我们给它标最小的号，于是问题就变成了求解从\(1\)号点出发，期望经过每个边的次数，我们设\(f[i]\)表示，到点\(i\)的期望次数，考虑写出转移方程

    \[f[u]=\begin{cases}\sum_{v\in \text{connect}(u)}\frac{f[v]}{\deg v}+1~~~(i=1)\\\sum_{v\in \text{connect}(u)}\frac{f[v]}{\deg v}~~~(2 \le i \le n)\end{cases}\]

    由于转移关系会成环，我们无法直接进行递推求解，所以接下来，我们对\(f[i]\)进行高斯消元，解出后，我们类比上文的方法\(2\)，对于一条边\(u,v\)，它的期望经过次数为

    \[\frac{f[u]}{\deg u}+\frac{f[v]}{\deg v}\]

    时间复杂度\(\mathcal O(n^3)\)

    矩阵快速幂优化dp

    寻址连续优化

    for(int i = 1; i <= n; i++)        for(int k = 1; k <= n; k++)            if(a.a[i][k])            for(int j = 1; j <= n; j++)                c.a[i][j] = (c.a[i][j] + 1ll * a.a[i][k] * b.a[k][j]) % mod;

    P3216 [HNOI2011]数学作业 （普通套路）

    题目

    \(f(i)\) 表示将 \(1\sim i\) 的数顺次拼接得到的一个数,计算 \(f(n)\mod m\)

    \(n\le 1\times 10^{18},m\le 1\times 10^9\)

    题解

    设 \(k\) 为 \(i\) 的位数,转移为

    \[f[i]=f[i-1]\times 10^k+i\]

    然后有

    \[\begin{bmatrix}f_i\\i\\1\end{bmatrix}\times\begin{bmatrix}{10^k}&{1}&{1}\\{0}&{1}&{1}\\{0}&{0}&{1}\end{bmatrix}\times \begin{bmatrix}f_{i-1}\\i-1\\1\end{bmatrix}\]

    CF514E Darth Vader and Tree （较大矩阵的矩阵快速幂）

    题面

    有一个无限大的有根树，树上的每一个节点都有 \(n\) 个子节点（\(1 \leq n \leq 10^5\)），任意一个节点它的第 \(i\) 个子节点之间的距离为 \(d_i\)（\(1 \leq d_i \leq 100\)）。

    给出一个数 \(x\)（\(0 \leq x \leq 10^9\)），求有多少个节点到根节点的距离小于等于 \(x\)，输出答案对 \(10^9+7\) 取模后的结果。

    题解

    设 \(f_i\) 表示到根节点距离恰好为 \(i\) 的方案数

    显然有 \(f_i=\sum_{j=1}^n f_{i-d_j}\)

    实际上,我们只关心每种 \(d_i\) 有多少个,而且 \(d_i\) 只有 \(100\) 种,所以考虑离散化然后使用桶存,设 \(t_i\) 表示 \(s.t. d_k=i\) 的 \(k\) 的个数,那么转移方程可以改写为

    \[f_i=\sum_{j=1}^{100} f_{i-j}\times t_j\]

    设 \(\text{sum}_i=\sum_{k=1}^if_k\) ,预处理完前 \(100\) 组数之后,就有转移矩阵

    \[\begin{bmatrix}{1}&{t_1}&{t_2}&\cdots&{t_{100}}\\{0}&{t_1}&{t_2}&\cdots&{t_{100}}\\{0}&{1}&{0}&\cdots&{0}\\{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{0}&{0}&\cdots&{1}&{0}\end{bmatrix}\times\begin{bmatrix}\text{sum}_i\\ f_{i-1}\\ f_{i-2}\\ \vdots \\f_{i-100}\end{bmatrix}=\begin{bmatrix}\text{sum}_i\\ f_i\\ f_{i-1} \\ \vdots \\ f_{i-99}\end{bmatrix}\]

    P2579 [ZJOI2005]沼泽鳄鱼 （邻接矩阵与矩阵快速幂）

    题目

    给定 \(n\) 个点的无向图,图上有 \(m\) 只鳄鱼在游荡,它们会按时间出现在不同的位置,周期只能为 \(2,3,4\) 。给定起点终点,求经过 \(k\) 步后走到终点的方案数

    \(n\le 50,m\le 20,k\le 2\times 10^9\)

    题解

    \(2, 3, 4\) 的最小公倍数为 \(12\)

    所以开十二个邻接矩阵即可, 每个矩阵表示当前走一步的合法情况

    \(a[0]\) 表示走 \(12\) 步的矩阵, 即 \(12\) 个邻接矩阵之积

    \(\lfloor \frac{k}{12} \rfloor\) 个 \(a[0]\) 相乘使用快速幂, 在按顺序从 \(a[1]\) 乘到 \(a[k\% 12]\)

    答案为 \(a[0]^{k/12} \times a[1] \times a[2]\times \cdots s[k\%12]\)

    P3176 [HAOI2015]数字串拆分（对拆分函数的处理）

    题面

    题解

    首先,显然有

    \[f_1=1,f_n=\sum_{i=\max(n-m,1)}^n f_i\]

    注意到 \(f_i\) 可以化成矩阵 \(A^i\) 进行递推,而 \(f_{x+y}=A^x\times A^y=A^{x+y}\)

    令 \(\text{num}[i][j]\) 表示从第 \(i\) 位到第 \(j\) 位所表示的数的转移矩阵,考虑到矩阵有分配律,设 \(g_i\) 表示 \(g(\text{num}[1][i])\) 所以我们有

    \[g_i=\sum_{j=0}^{i-1}g_j\times A^{\text{num}[j+1][i]}\]

    举个例子

    \[g(12)=f(1+2)+f(12)=A^3+A^{12}=g_1\times \text{num}[2][2]+\text{num}[1][2]\]

    时间复杂度 \(\mathcal{O} (n^2m^3)\)

    CF576D Flights for Regular Customers （动态变化的图）

    题目

    • 给定一张 \(n\) 个点 \(m\) 条边的有向图。
    • 一开始你在 \(1\) 号节点，你要走到 \(n\) 号节点去。
    • 只有当你已经走过了至少 \(d_i\) 条边时，你才能走第 \(i\) 条边。
    • 问最少要走多少条边，或判断无法到达。
    • \(n,m \le 150\)，\(d_i \le 10^9\)。

    题解

    首先对边按照 \(d_i\) 排序，从小到大依次加入每条边，动态维护能够到达的点，假设此时加入的边的 d 值为 t，矩阵加速求出当前图能够走到的所有的点

    每个点的状态只有 0/1 两种，分别对应着无法到达和可以到达,因此可以 bitset 优化，时间复杂度 \(\mathcal O(\frac{n^3m \log d}w)\)

    P6772 [NOI2020] 美食家 （拆点和预处理倍增矩阵）

    题目

    题解

    首先,边长 \(w\le 5\), 不能直接快速幂计算,但是可以进行拆点

    具体来说,就是将点 \(u\) 拆解为 \(u_1\rightarrow u_2\rightarrow u_3\rightarrow u_4\rightarrow u_5\)，边权为 \(0\) 边长为 \(1\) 那么对于原图中的一条边 \((u,v,w)\) 我们连的边是 \(u_w\rightarrow v_1\)边权为 \(c_u\) 边长为 \(1\) 。至此我们得到了一个 \((nw)^2\) 大小的矩阵

    至于美食节的条件,我们参考 CF576D 的做法,将 \(t_i\) 进行排序,分段处理,此时时间复杂度是 \(\mathcal{O}((nw)^3\sum \log (t_i-t_{i-1}))\) 矩阵快速幂的次数太多了,无法通过本题

    考虑优化,我们发现这一次次的矩阵快速幂中,每次都倍增着去做显然是有重复计算的,因此我们可以用 \(\mathcal O((nw)^3\log T)\) 的复杂度计算出倍增所需要的矩阵 \(P_i=A^{2^i}\) ,这样我们每次计算的时候就有原来快速幂时的矩阵乘矩阵优化为了向量乘矩阵,复杂度下降到了平方级别,平衡和复杂度,此时的时间复杂度是 \(\mathcal{O}((nw)^3\log T+(nw)^2\log (t_i-t_{i-1}))\) ,能够通过本题

    区间dp

    P1880 [NOI1995] 石子合并（破环成链+石子合并类套路）

    题目

    在一个圆形操场的四周摆放 \(N\) 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 \(2\) 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

    试设计出一个算法,计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。

    \(1\leq N\leq 100\)，\(0\leq a_i\leq 20\)。

    题解

    环形的序列,那么断开环,倍长序列去做

    设 \(f[l][r]\) 表示合并区间 \([l,r]\) 中的所有石子所能带来的最大收益,\(sum[l][r]\) 表示 \([l,r]\) 中石子个数的和,转移方程如下

    \[f[l][r]=\max_{l\le k\le r}\lbrace f[l][k]+f[k+1][r]+sum[l][r]\rbrace\]

    时间复杂度为 \(\mathcal O(n^3)\),可以使用四边形不等式优化到 \(\mathcal{O} (n^2)\) ,但这不是提高组的考察范围

    HDU 4283 You Are the One （栈的性质+石子合并类套路）

    题目

    有一个长为 \(N~(N\le 100)\) 的队列，第 \(i\) 个人有一个愤怒值 \(D_i\)，如果他是第 \(K\) 个上场，不开心指数就为 \((K-1)\cdot D\)。但是边上有一个小黑屋（后进先出，当成个堆栈），可以一定程度上调整上场顺序，使不开心指数最小

    题解

    考虑栈的性质,第 \(i\) 个元素入栈，如果它最终的位置是在 \(k\)，那么 \(i\) 到 \(k\) 这一段中不可能有 \(k\) 位置后的数出现。因此把问题 \([l,r]\) 分为子问题 \([l+1,k]\),\([k+1,r]\),直接转移即可

    时间复杂度 \(\mathcal{O}(N^3)\)

    P1005 [NOIP2007 提高组] 矩阵取数游戏 （取两端套路）

    题目

    题解

    首先一轮一轮的考虑是困难的,所以我们一行一行的考虑

    这样原问题可以转化对每一行确定选数的顺序

    那么就可以通过区间dp转移了,假设要选完 \([l,r]\) 中的数,由于每次只能取两边的数,那么就从 \([l,r-1]\times 2\) 或者 \([l+1,r]\times 2\) 转移而来

    时间复杂度 \(\mathcal{O}(mn^2)\)

    P3205 [HNOI2010]合唱队 （取两端套路+增加维数）

    题目

    题解

    考虑对理想队形进行区间dp,假设此时考虑排成区间 \([i,j]\) 队形的方案数,但是如果采取普通的 \(f[i][j]\) 的二维dp考虑,我们发现我们无法转移

    原因是我们dp的状态中缺少上一次的值放在了那里这一个信息,所以将状态修改为 \(f[i][j][0/1]\) 表示排成区间 \([i,j]\) 中的队形且第 \(i\) 个人在左端/第 \(j\) 个人在右端时的方案数

    转移如下

    if(a[i]a[i])f[i][j][1]+=f[i][j-1][0];if(a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];

    初始状态注意把所有的数都当成从左边进来的,不然会算重,时间复杂度 \(\mathcal{O}(n^2)\)

    P1220 关路灯 （提前计算贡献）

    题目

    题解

    首先考虑如果经过一个灯而不关掉它显然是不优的,所以每次关掉的灯一定是一段连续的区间

    于是设 \(f[i][j][0/1]\) 表示关掉了区间 \([i,j]\) 中所有的灯之后,身处最左端/右端时的所有的灯总的功耗和

    那么就有转移

    f[l][r][0]=min(f[l+1][r][0]+(p[l+1]-p[l])*(pre[l]+pre[n]-pre[r]),f[l+1][r][1]+(p[r]-p[l])*(pre[l]+pre[n]-pre[r]));f[l][r][1]=min(f[l][r-1][1]+(p[r]-p[r-1])*(pre[l-1]+pre[n]-pre[r-1]),f[l][r-1][0]+(p[r]-p[l])*(pre[l-1]+pre[n]-pre[r-1]));

    其实这本质是个贪心, \(\text{dfs}\) 也是可以做的

    时间复杂度 \(\mathcal{O}(n^2)\)

    P4170 [CQOI2007]涂色 （涂色类套路）

    题目

    给定一个长度为 \(n~(n\le 500)\) 的木板,初始没有颜色。

    我们现在要在上面涂色,每次涂色必须涂连续的一段区间且可以覆盖之前涂过的颜色

    问使初始木板变成目标颜色的最小操作次数

    题解

    设 \(f[i][j]\) 表示将区间 \([i,j]\) 中的位置变成目标颜色的方案数

    那么考虑分类讨论

    • 若 \(i=j\),则有 \(f[i][j]=1\)

    • 若 \(\text{col}[i]=text{col}[j]\) ,那么我们直接在端点处染色即可

    • 若 \(\text{col}[i]\neq \text{col}[j]\) ,那么我们就枚举一个分界点,左右两边涂不同的颜色

    状态转移如下

    if(l==r) f[l][r]=1else if(s[l]==s[r]) f[l][r]=min(f[l+1][r],f[l][r-1]);else if(s[l]!=s[r]) for(int k=l;k

    时间复杂度 \(\mathcal{O}(n^3)\)

    HDU 2476 String painter （分步涂色）

    题目

    给定两个初始串 \(\text{a},\text{b}\) ,求将 \(\text{a}\) 区间染色成 \(\text{b}\) 的最小步数

    \(|a|=|b|\le 500\)

    题解

    首先一个朴素的思路是直接设 \(f[i][j]\) 表示将 \(\text{a}\) 中的 \([l,r]\) 染成 \(\text{b}\) 的最小步数

    但是你要分十万种情况讨论,理论可行,但不可做

    所以我们考虑这样一个过程,我们可以先计算从无色串到 \(\text{b}\) 的最小步数,这就是“Luogu P4170 [CQOI2007]涂色”,然后我们对 \(\text{a}\) 进行一个dp求出它那些位置需要染色,假设我们求出无色串染色区间 \([l,r]\) 染成 \(\text{b}\) 的最小次数为 \(f[l][r]\)

    考虑如何对 \(a\) 序列进行dp,设 \(g[i]\) 表示考虑将 \(\text{a}\) 的前 \(i\) 位染色至 \(\text{b}\) 的最小的方案数,考虑如何进行转移,假设当前考虑到第 \(i\) 位

    • 如果 \(\text{a}[i]=\text{b}[i]\) ,那么 \(g[i]=g[i-1]\) 无需染色
    • 如果 \(\text{a}[i]\neq \text{b}[i]\) ,那么我们枚举染色的分界点 \(j\),转移方程为
    \[g[i]=\min_{1\le j\le i-1}g[j]+f[j+1][i]\]

    时间复杂度 \(\mathcal{O}(n^3)\)

    P7914 [CSP-S 2021] 括号序列（通过增维实现对不同情况的分类讨论）

    题目

    题解

    首先,朴素的思路是设 \(f[i][j]\) 表示区间 \([l,r]\) 中合法的超级括号序列的数量,但是我们注意到题目中有“连续的 \(*\) 不超过 \(k\) 个”这一个条件,所以我们记录的这个状态记录的信息不够,所以考虑增维

    设 \(f[i][j][p],p\in [0,5]\) , \(\text{A}\) 表示左右两边都是括号且这两个括号不匹配的串,其中

    • \(p=0\) 表示全是 \(*\) 的情况
    • \(p=1\) 表示 \((\text{A})\) 的情况
    • \(p=2\) 表示 \(\text{AS}\) 的情况
    • \(p=3\) 表示 \(\text{A}\) 的情况,注意该状态包含 \(p=1\) 的状态
    • \(p=4\) 表示 \(\text{SA}\) 的情况
    • \(p=5\) 表示 \(\text{SAS}\) 的情况,注意该状态包含 \(p=0\) 的状态

    下面我们来考虑转移,思路就是在已有的 \(2,3,4,5\) 后边接上 \(0,1\) 这两个基本单位来转移

    • \(p=0\) 时,对 \(\text{len}\) 进行一个特判即可
    • \(p=1\) 时,如果当前区间 \([l,r]\) 的左右端点不匹配则为 \(0\) ,否则注意一下转移时不能有 \((SAS)\) 的情况,于是转移为
    \[f[l][r][1]=f[l+1][r-1][0]+f[l+1][r-1][2]+f[l+1][r-1][3]+f[l+1][r-1][4];\]
    • \(p=2\) 时,我们就是要拿 \(\text{A}\) 拼上 \(\text{S}\) ,这里不拿 \(\text{AS}\) 拼 \(\text{S}\) 是为了满足长度不超过 \(k\) 的方案数,于是转移如下
    \[f[l][r][2]=\sum_{i=l}^{r-1}f[l][i][3]\times f[i+1][r][0]\]
    • \(p=3\) 时,我们可以通过 \(\text{AS}\) 拼上 \(\text{(A)}\) 或者 \(\text{A}\) 拼上 \(\text{(A)}\) ,注意加上 \(p=1\) 的情况
    \[f[l][r][3]=\sum_{i=1}^{r-1}(f[l][i][2]+f[l][i][3])\times f[i+1][r][1]+f[l][r][1]\]
    • \(p=4\) 时,我们就是要找开头为 \(*\) 的即 \(\text{SA},\text{SAS}\) 的后面拼接 \((A)\)
    \[f[l][r][4]=\sum_{i=1}^{r-1}(f[l][i][4]+f[l][i][5])\times f[i+1][r][1]\]
    • \(p=5\) 时,我们就是要找开头为 \(*\) 的即 \(\text{SA}\) 的后面拼接 \(S\) ,另外别忘了还有 \(\text{S}\)
    \[f[l][r][5]=\sum_{i=1}^{r-1}f[l][i][4]\times f[i+1][r][0]+f[l][r][0] \]

    答案必须为首尾都是括号序列.所以就为 \(f[1][n][3]\)

    这样dp的时间复杂度为 \(\mathcal{O}(n^3)\)

    数位dp

    数位dp的一般套路

    问题形式

    给你一个条件 \(A\) ,然后询问值大小在 \([L,R]\) 中有多少满足条件的数

    这个问题暴力去做一般是 \(\mathcal{O}(R)\) 的时间复杂度,但是通过数位dp我们可以把这个东西优化到 \(\mathcal{O}(\log_{10}R)\)

    求解过程

    首先我们将区间 \([L,R]\) 的限制利用前缀和拆开,这样我们的问题就变成了求 \([1,R]\) 中满足要求的数的个数

    每一位作为dp的阶段,设计状态,一般采用记忆化搜索的方法

    我们要从高位向低位枚举,因为如果我们确定的高位之后才可以确定低位的范围

    比如说一个数 \(1230\)

    如果我们前两位分别选的是 \(1,2\) ,那么第三位的取值范围就是 \([0,3]\)

    如果我们前两位分别选的是 \(1,1\) ,那么第三位的取值范围就是 \([0,9]\)

    也就是我们在记忆化搜索的过程中记一个变量 \(lim\) 表示前几位是否和最大数一样

    具体的代码实现看下面的这一道题目

    P4127 [AHOI2009]同类分布（经典数位dp）

    题目

    给出两个数\(a,b\)，求出\([a,b]\)中各位数字之和能整除原数的数的个数。

    \(1 \le a \le b\le 10^{18}\)

    代码实现如下,细节都在注释里

    #includeusing namespace std;#define int long longinline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=="-") f=-1;for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);return x*f;}const int N=25,M=210;int n,a[N],f[N][M][M],mod;inline int F(int u,int sum,int st,bool lim){if(u>n&&sum==0) return 0;//模数为0是无意义的 if(u>n) return st==0&&sum==mod?1:0;//如果模数恰好为1,那么就是一个合法的解 if(!lim&&f[u][sum][st]!=-1) return f[u][sum][st];//记忆化搜索 int ret=0,res=lim?a[u]:9;//lim判断当前位是否能随便取 for(int i=0;i<=res;++i) ret+=F(u+1,sum+i,(10*st+i)%mod,i==res&&lim); return f[u][sum][st]=ret;}inline int solve(int x){n=0;while(x) a[++n]=x%10,x/=10;reverse(a+1,a+1+n);//从高位到低位枚举 int ret=0;for(mod=1;mod<=9*n;++mod)//枚举当前模数 {memset(f,-1,sizeof(f));ret+=F(1,0,0,1);}return ret;}int l,r;signed main(){l=read();r=read();printf("%lld\n",solve(r)-solve(l-1));return 0;}

    HDU 3709 Balanced Number（普通数位dp）

    题目

    求区间 \([L,R]\) 里面满足平衡数的数的个数,\(1 \le L\le R\le 1\times 10^{18}\)

    平衡数定义：可以通过找一个平衡数位，该数位左边的数位乘以偏移距离的和等于右边的数位乘以偏移距离的和。

    比如 \(4139\) ，平衡数位为 \(3\) ,\(4\times 2+1=9\),因此该数是平衡数

    题解

    显然的是,每个数最多只能有一个平衡数位(毕竟没有物体是有两个重心的)

    那么我们仿照上一题枚举模数的做法,这一题我们枚举平衡数位

    假设我们将一个数的各位存到 \(a\) 数组中,枚举到的平衡数位是 \(k\) ,那么一个有 \(\text{len}\) 位的数答案可以按照如下的方式统计

    \[\text{nw}=\sum_{i=1}^{\text{len}} (i-k)\times a[i]\]

    当 \(i=\text{len}\) 且 \(\text{nw}=0\) 的时候,就意味着当前数是平衡数位为 \(k\) 的平衡数

    通过上面的方式统计出答案即可

    HDU 4507 吉哥系列故事——恨7不成妻（平方和的处理）

    题目

    如果一个数跟 \(7\) 有关,那么我们就说它满足以下三条性质

    • 整数中的某一位是 \(7\)
    • 整数的每一位上的数加起来是 \(7\) 的倍数
    • 整数是 \(7\) 的倍数

    询问 \([L,R]\) 当中与 \(7\) 无关的数的平方和 \(1\le L\le R\le 1\times 10^{18}\)

    题解

    首先可以通过所有的数的平方和减去与 \(7\) 有关的数的平方和来得到答案

    我们的状态按照下面的思路定义

    1. 整数中的某一位是 \(7\) \(\Rightarrow\) 一维状态 \(a\) 表示是否有 \(7\) 出现
    2. 整数的每一位上的数加起来是 \(7\) 的倍数 \(\Rightarrow\) 一维状态 \(b\) 表示各数位的和模 \(7\) 的值
    3. 整数是 \(7\) 的倍数 \(\Rightarrow\) 一维状态 \(c\) 表示当前这个数模 \(7\) 的值

    于是我们就设出了状态 \(f[u][a][b][c]\)

    如果是要求个数,那么这个问题与上面两个问题是没有区别的,可是这里是要我们求平方和

    所以考虑一个我们在期望dp那里也用过的套路,为了转移,我们需要维护 \(3\) 个值:

    • \(\text{cnt}\) 表示与 \(7\) 有关的数的个数
    • \(\text{sum}\) 表示与 \(7\) 有关的数的和
    • \(\text{sqr}\) 表示与 \(7\) 有关的数的平方和

    考虑转移,假设我们记忆化搜索回溯上来的数为 \(x\) ,当前是第 \(u\) 位,上面的数为 \(k\) 。那么我们知道,算上这一位后再回溯这个数就会变为 \(x+k\times 10^{u-1}\),为了方便表示,我们设 \(d=k\times 10^{u-1}\) ,考虑我们形成的新数 \(x+d\) 与 \(7\) 有关的数的平方和应该怎么计算

    它的平方对答案的贡献为 \((x+d)^2=x^2+2dx+d^2\) ,考虑如何计算这个贡献和,假设有 \(n\) 个合法的数分别为 \(x_1,x_2,\cdots ,x_n\) ,那么对答案的贡献如下

    \[\sum_{i=1}^n (x_i+d)^2=n\times d^2+2d\times (x_1+x_2+\cdots+x_n)+(x_1^2+x_2^2+\cdots+x_n^2)\]

    假设我们当前状态是 \(f\) ,回溯过来的状态是 \(g\) ,那么转移方程如下

    \[f.\text{cnt}\leftarrow g.\text{cnt}f.\text{sum}\leftarrow g.\text{sum}+d\times g.text{cnt}f.\text{sqr}\leftarrow g.\text{cnt}\times d^2+2d\times g.\text{sum}+g.\text{sqr}\]

    这样就做完了

    CF55D Beautiful numbers （数位dp的状态剪枝）

    题目

    Volodya 认为一个数字 \(x\) 是美丽的，当且仅当 \(x\in\mathbb{Z^+}\) 并且对于 \(x\) 的每一个非零位上的数 \(y\)，都有 \(y|x\)。

    你需要帮助他算出在区间 \([l,r]\) 中有多少个数是美丽的。

    \(t\) 组数据。

    \(1\le t\le 10,1\le l\le r\le 9\times 10^{18}\)

    保证 \(l,r\) 都是整数

    题解

    首先,一个数能够被它的各个数位同时整除,等价于它能被各个数位的 \(\text{lcm}\) 整除

    而 \(1\sim 9\) 的 \(\text{lcm}\) 是 \(2520\)

    因此各个数位的 \(\text{lcm}\) 一定是 \(2520\) 的因子

    于是我们设 \(f[u][\text{lcm}][\text{nw}]\) 表示枚举到第 \(u\) 位,当前所有非零数位的 \(\text{lcm}\) 为 \(\text{lcm}\),当前这个数模 \(2520\) 的结果为 \(\text{nw}\) ,假设当前数位的值为 \(k\) ,所以有转移

    \[f[u][\text{lcm}][\text{nw}] \leftarrow f[u+1][\text{lcm}(\text{lcm},k)][(\text{nw}+k)\% 2520]\]

    由于中途的 \(\text{lcm}\) 是会发生变化的,所以我们模 \(2520\)

    最后检查 \(\text{nw}\% \text{lcm}\) 是否为零就行

    了吗？

    我们注意到 \(\text{lcm}\) 和 \(\text{nw}\) 都是 \(2520\) 的大小,所以你要是这么写了,那么恭喜 \(\text{MLE}\)

    注意到 \(2520\) 只有 \(48\) 个 因子,因此状压一下 \(\text{lcm}\) 那一维就可以了

    CF908G New Year and Original Order （经典数位dp）

    题目

    给 $ n\le 10^{700} $ ，问 \(1\) 到 \(n\) 中每个数在各数位排序后得到的数的和。

    题解

    首先直接做肯定是没有前途的,冷静一下,我们发现一个性质,这里以 \(2457\) 举例

    \[2457=1111\times 2+111\times 2|11\times 1+1\times 2+0\times 2\]

    于是我们发现,一个数各数位排序之后会形成一个单调不降的序列,可以将其拆分为 \(9\) 个形如 \(1\cdots 11\) 的数。换句话说,如果这个数中有 \(i\) 个数位是大于等于 \(d~(d\in [1,9])\) 的,那么其对答案的贡献就有 \(\underbrace{11\cdots 1}_{i}\)

    所以我们可以对于每个 \(d\) 都去算一下贡献,设 \(f[i][j][lim]\) 表示选了 \(i\) 个数,恰好有 \(j\) 位 \(\ge d\) ,是否压上界,时间复杂度 \(\mathcal O(n^2\times 10)\)

    计数dp

    错位排列计数 （组合意义dp）

    题目

    给定长度为 \(n\) 的排列,求解其错位排列数

    题解

    设 \(D_n\) 表示长度为 \(n\) 的排列的错排数,考虑我们已经知道了前 \(n-1\) 个错排数,那么对新加入的这第 \(n\) 个数进行分类讨论

    • 直接与前面的数交换,有 \((n-1)\times D_{n-2}\) 种方案
    • 放在前面某个数的位置上,那么相当于给原来 \(n-1\) 个数做了错排,有 \((n-1) \times D_{n-1}\) 中方案所以
    \[D_n=(n-1)\times (D_{n-1}+D_{n-2})\]

    这个递推式可以求出其通项,但这不是本博客讨论的范围,读者感兴趣的自行了解即可

    NOIP 四校联测 Day1 T2 （组合意义dp）

    题目

    给定两个排列 \(A,B\),求字典序介于 \(A,B\) 之间的排列最大前缀个数恰好为 \(k\) 的排列的个数

    \(|A|,|B|\le 3000\)

    题解

    首先我们考虑没有字典序的限制要怎么做,设 \(f[i][j]\) 表示倒着往前考虑到第 \(i\) 个数,最大前缀个数为 \(j\) 时的排列的个数,转移时考虑组合意义

    \[f[i][j]=f[i-1][j-1]+(i-1)\times f[i-1][j]\]

    也就是我们当前的 \(i\) 是最小的那个数,我们考虑它如果放在最前面,那么前缀最大值的个数会 \(+1\),否则不会发生改变

    考虑正解

    一眼丁真,类似数位dp,应该是要进行一个差分的,也就是 \(\ge a\text{数的个数}-\ge b\text{数的个数}\)

    于是我们考虑从前到后枚举每一位,以 \(\ge a\text{数的个数}\) 为例,假设 \(i\) 位之前都是相同的,我们枚举每一个在 \(A\) 数组的前 \(i-1\) 个位置没有出现过，而且比 \(a[i]\) 大的数字 \(B\) 填到位置 \(i\) 上因此前 \(i\) 个位置我们已经填好了，且消除了对后面字典序的限制

    考虑 \(1\sim n\) 中没有在前 \(i\) 个位置出现过的数字的集合为 \(S\) ，设我们已经填了的数字的最大值为 \(\text{mx}\) ，则 \(S\) 集合中所有小于 \(\text{mx}\) 的数字，都不会对前缀最大值的个数产生贡献

    设前 \(i\) 个位置中，前缀最大值的个数为 \(C\) ，\(S\) 集合中大于 \(\text{mx}\) 的数字个数为 \(D\),那么有我们在 \(i+1\sim n\) 必须整出 \(k-C\) 个前缀最大值才可以

    而 \(S\) 集合中小于 \(\text{mx}\) 的数是可以随便填的,所以当前对答案的贡献就是

    \[\binom{D}{k-C}\times f[D][k-C] \times (n-i-D)!\]

    然后把所有 \(i\) 对应的答案加起来就行了,时间复杂度 \(\mathcal{O} (nk)\)

    NOIP 四校联测 Day2 构造数组 （辨认无意义的状压dp+组合意义dp）

    题目

    你现在有一个长度为 \(n\) 的数组 \(a\)。一开始，所有 \(a_i\) 均为 \(0\)。给出一个同样长度为 \(n\) 的目标数组 \(b\)。求有多少种方案，使得通过若干次以下操作，可以让 \(a\) 数组变成 \(b\)。

    • 选出两个不同的下标 \(1\leq i

    两种方案被称之为不同的，当且仅当存在一个 \(x\) 使得一种方案中第 \(x\) 次操作选择的两个下标 \((i,j)\) 与另一种方案中的不同。

    \(1\le n\le5~000\)，\(1\leq b_i\le30~000\)，\(\sum b_i\le30~000\)

    题解

    这道题感觉出的挺好的,部分分给的挺多的,正解是不太好想的,考场上花了好长时间想,最后也没调出来

    首先我们可以将这个问题转化成,我现在有 \(\frac{n}{2}\) 个容量为 \(2\) 的桶,然后我要往这些桶里面放东西。

    一种朴素的状压dp做法是,考虑设 \(f[i][s]\) 表示考虑到第 \(i\) 个元素,各个桶的放置情况是 \(s\) 时的方案数。

    然而我们发现我们其实并不关心每个桶放数的情况,我们只关心放了 \(0\) 个,\(1\) 个,\(2\) 个桶的数的个数,因此我们可以将状态设为 \(f[i][j][k]\) 表示考虑到第 \(i\) 个元素,个数为 \(1\) 的桶有 \(j\) 个,个数为 \(2\) 的桶有 \(k\) 个时的方案数,这样可以推出个数为 \(0\) 的桶的个数,转移时枚举当前元素有多少分给了 \(0\) ,多少分给了 \(1\) ,组合数计算转移即可

    更进一步,我们发现知道了个数为 \(2\) 的桶的数量,我们是可以计算出考虑到第 \(i\) 个元素时个数为 \(1\) 的桶的数量的(因为前面的桶一定要全选完,不然没法跟后面的桶配对),转移同上

    时间复杂度 \(\mathcal O\left((\sum b_i)^2\right)\)

    容斥原理套路于DP

    参考本校学长ylxmf2005的博客,容斥原理在dp中有如下的经典应用:

    1. $\text{一个也没有}=\text{全部都有}-\text{至少一个}+\text{至少两个}-{至少三个}+\cdots $
    2. \(\text{所有限制}=\text{没有限制}-\text{一个限制}+\text{两个限制}-\cdots\)
    3. \(\text{恰好有}k\text{个}=\text{至少有}k\text{个}-\binom{k+1}{k}\text{至少有}k+1\text{个}+\binom{k+2}{k}\text{至少有}k+2\text{个}-\cdots\)
    4. \(\text{min-max容斥}\) \(\max(s)=\sum_{t\subset s}(-1)^{|t|-1}\min(t)\)

    一般容斥原理直接暴力做的复杂度是 \(\mathcal O(n2^n)\),需要我们用dp或者多项式进行优化

    P5664 [CSP-S2019] Emiya 家今天的饭 （容斥原理套路1）

    题目

    题解

    首先,如果直接考虑本题合法的方案数,我们发现题目中的限制有些过于多了,正难则反,考虑容斥

    所以我们可以钦定一定有某一种食材超过了限制,那么答案就是总的方案数减去不合法的方案数。设 \(f[i][j][k]\) 表示考虑到第 \(i\) 种烹饪方法,超限食材使用了 \(j\) 次,其它食材使用了 \(k\) 次的方案数; \(\text{sum}\) 表示第 \(i\) 种烹饪方式所能做的菜的种类的和。那么枚举当前考虑的食材是 \(c\) ,那么有转移

    \[f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]\times a[i][c]+f[i-1][j][k-1]\times (\text{sum}[i]-a[i][c])\]

    不合法的方案数就是

    \[\sum_{j> k} f[i][j][k] \]

    设 \(g[i][j]\) 表示考虑到第 \(i\) 种烹饪方式,使用了 \(j\) 种食材时的总方案数,转移为

    \[g[i][j]=g[i-1][j]+\text{sum}[i]\times g[i-1][j-1]\]

    于是

    \[\sum_{i=1}^{k} g[n][i]\]

    就是我们的总方案数

    综合来看,我们目前的时间复杂度是 \(\mathcal O(n^3m)\) 的,无法通过本题,于是考虑优化

    这就是这道题最经典的地方了,我们发现对于 \(j,k\) 这两维,我们最后统计答案的时候关心的仅仅只是它们的相对大小关系,因此我们更改状态为 \(f[i][j]\) 表示考虑到第 \(i\) 种烹饪方式,钦定的使用数量最多的那一种食材相对其它食材的总和的差为 \(j\),那么转移就变成了

    \[f[i][j]=f[i-1][j]+f[i][j-1]\times a[i][c]+f[i-1][j+1]\times (\text{sum}[i]-a[i][c])\]

    于是时间复杂度就降为了 \(\mathcal O(n^2m)\)

    P1450 [HAOI2008] 硬币购物 （容斥原理套路1）

    题目

    共有 \(4\) 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。

    某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了 \(d_i\) 枚 \(i\) 种硬币，想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。

    \(1 \leq c_i, d_i, s \leq 10^5\)，\(1 \leq n \leq 1000\)。

    题解

    与上一道题同理,直接利用分组背包计算合法的方案数肯定是T飞了的,所以同样考虑容斥

    我们分别钦定有 \(1\) 种, \(2\) 种, \(3\) 种 ,\(4\) 种硬币超过了限定了数量,没有限定的硬币随便选,假设当前选择的超限硬币组成的集合为 \(S\) 那么我们每次就相当于做一个背包容量为 \(s-\sum_{i\in S}(d_i+1)\times c_i\) 的完全背包,容斥一下,奇加偶减即可,这个时间复杂度就降为了 \(\mathcal O(n)\) ,采用预处理完全背包的做法的话带一个 \(4\) 的常数,不预处理也是可以通过的

    BZOJ3622 已经没什么好害怕的了 （容斥原理套路3）

    题目

    给定 \(a\),\(b\) 两个长度均为 \(n\) 的数列,我们现在要对它们进行两两配对,问配对后 \(a\) 比 \(b\) 大的个数比 \(b\) 比 \(a\) 大的个数多 \(k\) 组的方案数

    \(n\le 5000\)

    题解

    无序的序列过于丑陋,所以我们先要对两个序列先进行一个排序

    设 \(p[i]\) 表示使得 \(b[j]

    同样与上一题类似,设 \(f[i][j]\) 表示考虑到 \(a\) 序列的第 \(i\) 位,已有 \(j\) 组 \(a>b\) 的方案数,剩下的随意分配,即对于所有的 \(f[n][i]\) 都要乘上一个 \((n-i)!\)

    我们想要的就是 \(a>b\) d的组数恰好为 \(\frac{n-k}{2}\) 的方案数

    我们现在对 \(f[n][i]\) 中 \(i > \frac{n-k}{2}\) 的部分进行一个容斥,令 \(m=\frac{n-k}{2}\) ,那么就有

    \[\text{ans}=\sum_{i=m}^n(-1)^{i-m}\binom{i}{i-m}f[n][i]\]

    时间复杂度 \(\mathcal O(n^2)\)

    HDU 4336 Card Collector （容斥原理套路4 min-max容斥）

    题目

    有 \(n\) 张卡牌，每次拆开一包方便面有 \(p_i\) 的概率得到第 \(i\) 张卡牌，保证 \(p_1 + p_2 + \cdots + p_n \le 1\) , 所以方便面里可能存在没有牌的情况，求收集完 \(n\) 张卡牌，需要拆开的方便面包数的期望

    题解

    \(\text{min-max容斥}\) 常用于解决形如“全部出现的期望时间”问题，处理方法如下：

    记 \(t_i\) 为第 \(i\) 个物品出现的时间, \(\min(S)\) 表示集合 \(S\) 中的物品至少一个出现的期望时间,\(\max(S)\) 表示集合 \(S\) 中的物品全部出现的期望时间

    又因为单位时间内 \(S\) 中出现至少一个的概率为 \(p\),那么在 \(S\) 中出现至少一个的期望时间就是 \(\frac{1}{p}\)

    所以,对于本题,

    \[\min(S)=\frac{1}{\sum_{i\in S}p_i}\]

    我们套用 \(\text{min-max容斥}\) 的公式就可以过掉这道题了

    时间复杂度 \(\mathcal O(2^n)\)

    ARC101E Ribbons on Tree (容斥原理套路2)

    题目

    给定一个 \(n\) 个点的树,\(n\) 为偶数,点与点之间两两配对,配对点之间的边被覆盖,问有多少种配对方式,使得每一条边都有被覆盖

    \(n\le 5000\)

    题解

    直接计算是 \(\mathcal O(n^3)\) 的,无法通过本题

    所以考虑容斥,设 \(S\) 表示没有被覆盖的边的集合,将这些视作断掉的边,那么就有

    \[\text{ans}=\sum_{S\subset E} (-1)^{|S|}f(S)\]

    其中 \(f(S)\) 表示不能覆盖到 \(S\) 中边的方案数,那么答案就是

    \[\text{ans}=\sum_{S\subseteq E}(-1)^{|S|}f(S)\]

    设 \(g(n)\) 表示 \(n\) 个点任意配对的方案数,那么有 \(g(n)=n!!\) (双阶乘)

    设 \(\text{dp}[u][x]\) 表示结点 \(u\) 所在联通块大小为 \(x\) 时的方案数,注意此时 \(u\) 所在的联通块并没有独立出来,没有算在联通块总数中

    对于 \(x\ge 1\) 的情况,转移就是树上背包,复杂度证明与"BZOJ 4033 树上染色"是一样的

    对于 \(\text{dp}[u][0]\) 的情况,此时我们就将当前点 \(u\) 所在的联通块独立出来,也就是钦定了 \(u\) 到其父亲的这条边被删掉了,我们有 \(\text{dp}[u][0]=-\sum_{x=1}^{\text{siz}_u}\text{dp}[u][x]\times g[x]\) 因为此时被删掉的边集大小大了 \(1\)

    时间复杂度 \(\mathcal O(n^2)\)

    BZOJ 4767 两双手 （容斥原理套路2）

    题目

    棋盘上 \((0,0)\) 处有一个棋子。棋子只有两种走法，分别对应向量 \((A_x,A_y),(B_x,B_y)\)。同时棋盘上有 \(n\) 个障碍点 \((x_i,y_i)\)，棋子在任何时刻都不能跳到障碍点。求棋子从 \((0,0)\) 跳到 \((E_x,E_y)\) 的方案数。答案对 \(10^9+7\) 取模

    \(E_x,E_y,n\le 5000\),保证 \((A_x,A_y)\) 与 \((B_x,B_y)\) 不共线

    题解

    因为两个向量不共线,由平面向量基本定理,加之旗子只有两种走法,我们可以找到对于一个变换后坐标为 \((x_1,y_1)\) 的点 \(A\) 和坐标为 \((x_2,y_2)\) 的点 \(B\),那么从前者走到后者的方案数就是 \(\binom{x_2-x_1+y_2-y_1}{x_2-x_1}\),记这个方案数为 \(\text{cnt}[A][B]\)

    接着我们考虑容斥原理的套路 \(2\),设 \(f[i]\) 表示 \(i\)障碍之前不经过任何障碍到达障碍 \(i\) 的方案数,转移有

    \[f[i]=\text{cnt}[i][0]-\sum_{j=1}^{i-1}f[j]\times \text{cnt[j][i]}\]

    时间复杂度是 \(\mathcal O(n^2)\)

    ZR2022 NOIP十连测 Day5 T3 （数位dp+容斥原理套路1）

    题目

    小K想知道你可不可以帮他验算。

    小K有 \(k\) 个在 \([0,x]\) 范围内的随机整数 \(a_1,\ldots,a_k\)，记 \(f(x)\) 表示 \(x\) 的所有非零数位的积，例如 \(f(0)=1,f(1145141919810)=1\times1\times4\times5\times1\times4\times 1\times9\times1\times9\times8\times1f(0)=1,f(1145141919810)=1\times1\times4\times5\times1\times4\times 1\times9\times1\times9\times8\times1\)。现在小 \(k\) 想知道 \(f(\sum_{i=1}^ka_i)\) 的期望值。

    小K已经用超级计算机计算出了精确值，所以你只需要算出答案乘上 \((x+1)^k\) 对 \(10^9+7\) 取模的值帮他验算就好了

    \(k\le 20,n\le 10^{10^{4}}\)

    题解

    毒瘤题!

    乍一看就很像一个数位dp,但这道题困难的地方在于如何求出每一个 \(f(n)\) 它的系数是多少,并且如何将这个系数分离出来变成数位dp可做的东西

    然后难的就是这一部分,所以我把这题归到了计数dp中(尽管它看着更像是一个数位dp)

    我们设 \(g(n)\) 表示使得 \(\sum_{i=1}^ka_i=n\) 的方案数,那么考虑容斥,有

    \[g(n)=\sum_{i=0}^k(-1)^i\binom{k}{i}\binom{n-(x+1)i+k-1}{k-1}\]

    组合意义就是对大于 \(x+1\) 的数的个数进行容斥,后面那一部分考虑整体加一后插板

    于是我们要求的答案就变成了

    \[\begin{aligned}&\sum_{i=0}^{kx}f(i)g(i)\\=&\sum_{i=0}^{kx}f(i)\sum_{j=0}^{k}(-1)^j\binom{k}{j}\binom{i-(x+1)j+k-1}{k-1}\\=&\sum_{j=0}^{k}(-1)^j\binom{k}{j}\sum_{i=0}^{kx}\binom{i-(x+1)j+k-1}{k-1}f(i)\\=&\sum_{j=0}^{k}(-1)^j\binom{k}{j}\sum_{l=0}^{k-1}c_{j,l}\sum_{i=0}^{kx}f(i)i^l\end{aligned}\]

    其中

    \[c_{j,l}=[i^l]\binom{i-(x+1)j+k-1}{k-1}\]

    这个东西显然是可以 \(\mathcal O(k^4)\) 暴力做的

    这样我们的问题就转化为求

    \[\sum_{i=0}^{kx}f(i)i^l\]

    我们参考以往数位dp的经验,对上面那个式子进行转移,设 \(\text{dp}[j]=\sum_{i=0}^{kx} f(i)i^j\) ,假设我们枚举当前位 \(\text{now}\) 的取值为 \(x\) ,加完上一位时得到的数位 \(\text{num}\) 那么有转移

    \[\text{dp}[a+b] \leftarrow f(\text{num}+x\times 10^{\text{now}})\times (\text{num}+x\times 10^{\text{now}})^{a+b}\]

    即从

    \[\begin{aligned}&f(\text{num}+x\times 10^{\text{now}})\times (\text{num}+x\times 10^{\text{now}})^{a+b}\\=&\binom{a+b}{a}\times f(x)\times f(\text{num})\times \text{num}^b\times (x\times 10^{\text{now}}) ^a\\=&\binom{a+b}{a}\times f(x)\times \text{dp}[b]\times (x\times 10^{\text{now}}) ^a\end{aligned}\]

    转移而来最后注意 \(\binom{n}{m},(n< m)\) 时是 \(0\) ,而我们在算系数的时候会把这玩意算负,所以最后那个式子改成

    \[\sum_{j=0}^{k}(-1)^j\binom{k}{j}\sum_{l=0}^{k-1}c_{j,l}\sum_{i=j(x+1)}^{kx}f(i)i^l\]

    时间复杂度 \(\mathcal O(k^4+k^3\lg x)\)

    [SRM 697] ConnectedStates （prufer序列计数）

    题目

    有\(n\)个城市，每个城市有个权值\(w_i\)，任意两个城市\(i,j\)之间的道路数有\(w_i\times w_j\)条。对于每种生成树，若每个点的度数为\(d_i\),则贡献为 \(\prod d_i\)。求所有无根生成树的权值和。

    \(n\le 1000\)

    题解

    吐槽：真毒瘤

    这是一个有标号无根树问题，所以我们可以考虑搞出它的\(\text{prufer}\)序列，每个点的个数就是\(\text{prufer}\)序列中出现的次数\(+1\)

    对于一个固定的\(\text{prufer}\)序列(无根树)，方案总数显然是\(\prod w_i^{d_i}\)

    贡献就再乘上度数之积为\(\prod d_iw_i^{d_i}\)

    然后我们再算有多少种\(\text{prufer}\)序列，每个数都有一个出现次数的全排列显然是多重组合数，所以方案数有

    \[\frac{(n-2)!}{\prod(d_i-1)!}\]

    因此我们最终所要求的东西就是

    \[\sum_{\sum d_i=2n-2}\frac{(n-2)!}{\prod(d_i-1)!}\prod d_iw_i^{d_i}\\=(n-2)!\sum_{\sum d_i=2n-2}\frac{\prod d_iw_i^{d_i}}{\prod(d_i-1)!}\]

    设\(f[i][j]\)表示考虑到第\(i\)个数，度数和为\(j\)的方案数，枚举当前位的度数\(k\)，转移就乘上一个\(\frac{kw_i^{k}}{(k-1)!}\),这部分可以预处理出来

    所以暴力转移的复杂度是\(\mathcal O(n^3)\)的

    考虑使用多项式的幂公式，即

    \[(x_1+\cdots+x_t)^n=\sum_{\sum t_i=n}\binom{n}{t_1,t_2,\cdots t_n}\prod x_i^{t_i}\]

    我们令\(a_i=d_i-1\),那么有

    \[\begin{aligned}\text{原式}&=(n-2)!\sum_{\sum a_i=n-2}\binom{0}{a_1,a_2,\cdots,a_n}\prod (a_i+1)!w_i^{a_i+1}\\&=(n-2)!\prod w_i\sum_{\sum a_i=n-2}\binom{0}{a_1,a_2,\cdots,a_n}\prod (a_i+1)!w_i^{a_i}\end{aligned}\]

    现在我们离化简只差\(\prod (a_i+1)\)这个东西了，考虑它实际上是在枚举子集(枚举\(a_1\sim a_n\)几个相互组成的单项式)，我们考虑当前我们枚举到的单项式是\(a_2a_3a_7\),那么这个单项式对答案的贡献为(注意单项式被乘进了分母里,所以对应的加和也要减\(3\)),前面\((n-2)!\prod w_i\)就先不管了

    \[w_2w_3w_7\frac{1}{(n-5)!}\sum_{\sum a_i=n-5}\binom{n-5}{a_1,a_2-1,a_3-1,\cdots,a_n}w_i^{a_i}\\=w_2w_3w_7\frac{1}{(n-5)!}(w_1+\cdots+w_n)^{n-5}\]

    所以类比到整个式子就变成了

    \[(n-2)!\prod w_i \sum_{k=0}^{n-2}(\sum_{从n-2个里面选k个}\prod w_i)\frac{(w_1+\cdots w_k)^{n-2-k}}{(n-2-k)!}\]

    \(f[t][k]\) 表示只考虑使用前 \(t\) 个数组合，所有 \(k\) 项式之和是多少。转移就是 \(f[t][k]=f[t−1][k]+f[t−1][k−1]\times w_t\)那么这道题就可以 \(\mathcal O(n^2)\)

    关键词： 时间复杂度 容斥原理 转移方程