J题题解（ICPC Mid-Central USA Region 2019）

题意

请你统计所有满足m个约束的、长度为n的01序列的方案数。
约束会以如下形式给出：（1）l,r,"same"表示要求从下标l到下标r的01序列的值完全相同（全为0或全为1）；（2）l,r,"different"表示要求从下标l到下标r的01序列的值不完全相同

DP。

在约束条件那里。

“l,r,same”等价于从l到r染成同一种数字，因此跟r有关的状态看起来可以从l-1有关的状态那里转移过来（因为l到r都是同一种数字，可以把这个区间视为一个整体（或干脆就视为一个数字），这不会影响方案数）
“l,r,different”似乎比较难处理，因为我们并不知道“不完全相同”这个条件怎么利用，其实这个条件是对same的约束条件的某种约束，不妨在后面尝试推导DP的过程中思考怎么运用。

我们可以直接考虑O（n^2）的二维数组的DP，因为这个是允许通过的标准姿势。
设置状态

我们定义dp[i][j]，表示现在枚举到第i位，且从第j位到第i位都是同一个数字，并且第j位和第j-1位不是同一个数字的方案数。为什么要这样设置？这是出于方便统计答案的考量。这样设置状态不难发现最终答案为

$ans=\sum_{j=1}^{n}(dp[n][j])$

一般在敲定DP状态后，我们就可以直接思考转移方式。如果能推出来这道题就做完了，如果不能那么可以再尝试设置新的DP状态。好消息是这题情况属于前者。

建立转移

首先，根据DP状态的定义，我们有初始状态 dp[1][1]=2，这是因为第一位没有约束，总可以取0或取1.

我们先假设m=0，即没有任何same和different的约束。

我们先考虑dp[i][j]怎么从上一位的dp[i-1][j]转移过来。这里j>=1&&j<=i-1
可以写出转移

$dp[i][j]+=dp[i-1][j]$

这是因为根据我们的DP定义，第j位到第i位必须是同一个数字，所以说第i位和第i-1位也将会是同一个数字。我们上面提到过，他们的方案数是一样的，可以直接转移。
我们再考虑dp[i][i]怎么转移过来，考虑它的定义：第i位和第i-1位不一样的所有方案数。转移方程为

$dp[i][i]=\sum_{j=1}^{i}dp[i-1][j]$

而对于第i位和第i-1位一样的情况，我们已经在之前的dp[i][j]（j<i）的时候考虑到了。这样，对于没有约束条件的DP转移，我们就完成了。

下面我们考虑约束条件如何改变我们转移。

假设现在有一个约束条件：下标k到下标i必须是the same，那么形如dp[i][1],dp[i][2],dp[i][3],...,dp[i][k]都是合法的转移，因为他们满足约束条件；但是dp[i][k+1],dp[i][k+2],...,dp[i][i]都是不合法的转移，因为他们不满足the same的约束条件。
同样的，假设现在有一个约束条件：下标k到下标i必须是different，那么形如dp[i][k+1],dp[i][k+2],dp[i][k+3],...,dp[i][i]都是合法的转移，因为他们满足约束条件；但是dp[i][1],dp[i][2],...,dp[i][k]都是不合法的转移，因为他们不满足different的约束条件。
综合上面分析，我们发现：约束条件通过改变我们DP转移的枚举范围来限制方案数。于是我们可以写出最终的转移方程如下：

$dp[i][j]+=dp[i-1][j],j\in[diff[i]+1,same[i]]$

$dp[i][i]=\sum_{j=diff[i]+1}^{same[i]}dp[i-1][j]$

这里same[i]表示跟i相同的，最左边的那个下标，diff[i]表示跟i不完全相同的，最右边的那个下标。

最后我们再考虑一些无解的特殊情况，这道题就完成了。参考代码