分类： 递推计数

题目链接

题意：

给定一个 $n*m$ 的棋盘，每次你只能向右走或者向下走，要求从左上角 $(1,1)$ 走到右下角 $(n,m)$ ，问有多少种走法。
有一个限制因素是棋盘的格子里可能有石头，然后走到一个地方就会把这里的石头按照来的方向推出去，如果有多个石头就会连带着一起推过去。
数据范围 $1\le n,m\le 2000$ ，答案对 $10^9+7$ 取模。

题解：

直接DP会有后效性的问题，我们可以给状态加上约束：令 $D_{i,j} R_{i,j}$ 分别表示一个点改变原方向后向下走/向右走有多少种走法。
这样的话dp转移可以写成类似于 $D_{i,j}=\sum_{i=1}^{n-k-i}R_{i+t,j}$ 的形式，然后这样可以得到一个复杂度 $\mathcal{O}(n^3)$ 的算法，
观察这个式子发现他是线性的，当一个维度发生变化是等式右边只有一到两项会发生变化，就把复杂度降到了 $\mathcal{O}(n^2)$ ,就可以通过本题了。
继续阅读“[DP][后效性处理] codeforces 1247 E Rock Is Push”

题目链接

题意：给定ABC三个数，大小1e9，要求求出来1<=x<=A,1<=y<=B范围内满足(x&y)>C或(x^y)<C的(x,y)对数。

由于题目给的是或条件，所以还要考虑一个容斥的问题，先算出来单独满足两个条件的数目，再减去同时满足两个条件的数目，即可得到答案。先考虑单独计算两个条件的情况：

一般来说这种数位dp的框架都是类似的，在第i位时考虑前面的约束有没有“顶满”，如果顶满的话考虑当前这一位的限制，否则继续递归下去。这样的框架使得最后的递归边界处理变成了最有思维含量的一部分。这个题不同寻常的地方在于它是强制要求你同时考虑多个边界的，这是值得注意的一点。在这个题目里比较友好的一点是他对于与C的关系比对的时候是不等号，没有等号，这样的话，我们只要在dp计数的过程中一直保持可行性就可以了，到最后一步（pos=-1）只需要判断

1）前面是不是顶到C的头了，如果是的话就不行
2）前面是不是顶到了全0，因为题目要求x，y至少为1
继续阅读“[补题][数位dp][位运算] 2019牛客第七场 H Pair”

题目链接

题意：给定一个字符串S，长度为n≤100，然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里，每次操作的cost是(n-L)，然后问对于给定的k（k最大可取1e12），最少需要多少总cost才能使得set的元素个数达到k。难度2200分，有点虚高其实，不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的，感觉挺经典那种。他有一个easy version是k≤100，这个要求的话就很松了，mike的题解直接用了一种及其暴力的方法：把每个subsequence当作一个点，相差一个字符的点之间连边建图，直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法，但是k≤100的时候很快就能搜到，只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12，这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系，如果我们能求出来对应于某一长度j的unique子序列有多少个，那就可以解决这个问题了。这个就是一个引导方向，可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移，按照大问题转化为小问题的思想，dp[i][j]表示的以i结尾的unique子序列，那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列，数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息，这个一定是某些dp[pos][j-1]之和，但是有一种情况的是不同的pos对应的子串可能一样，所以这个题目最精彩的部分就来了，每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏，如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少，即不漏；第二这个就避免了重复计算的现象，不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
继续阅读“[DP][思维][×] codeforces 1183H Subsequences (hard version)”