LittleElephantAndBoard

作者：袁伟强

关键词：计数

题目简述

给一个$2\times M$的表格，现在你要将其中的$R$个格子涂成红色，$G$个格子涂成蓝色，$B$个格子涂成蓝色，并且要满足：任意两个相邻格子的颜色不同；每种颜色在任意一个$2\times 2$矩阵中都至少出现一次。求方案数对$10^{9}+7$取模。

$2\leq M \leq 10^{6}$

$R+G+B=2\times M$

问题的转化

我们先考虑逐列染色。容易发现，每一列的染色只和前一列的染色情况有关。事实上，由于每列的两个格子颜色不同，我们可以用这一列中没有出现的颜色表示该列。由于每种颜色在任意一个$2\times 2​$矩阵中至少出现一次，所以相邻两列的颜色都是不同的。例如某一列的染色为RG，颜色则为B；下一列的染色情况只可能为BR（颜色为G）或GB（颜色为R）。注意到一种颜色实际上对应着两种染色情况，如B对应着RG或GR，所以我们还要确定第一列的染色情况，之后的染色情况可以由颜色序列和第一列的染色情况唯一确定。

设$R'=M-R,G'=M-G,B'=M-B$，我们要求的就是有多少个长度为$M$的数组，其中有$R'$个元素为R，$G'$个元素为G，$B'$个元素为B，并且相邻两个元素不同的方案数$\times 2$。

算法

直接DP是$O(M^3)$的，显然无法接受。

如果确定了B的位置，我们需要在剩下的若干段空位中填上R和G。如果空位的长度是偶数，有RGR...RG和GRG..。GR两种填法，两种填法中G和R出现的次数都相同，不会对元素个数造成影响，我们把它们看成一类，记其数量为$x_{0}$，最后计算答案的时候要乘上$2^{x_{0}}$；如果空位的长度是奇数，有RGR...GR和GRG...RG两种填法，由于他们会对元素个数造成影响，需要分开考虑，分别记其数量为$x_{1}$和$x_{-1}$。

事实上，我们并不用关心B的具体位置。我们只需要确定每段空位的形态，在每段空位之间插入B即可。在这里，我们还需要考虑一个问题，就是开头和结尾也可以插入B。我们可以分为如下三种情况讨论：

（1）开头和结尾都是B，这样有$B'-1$段空位

（2）开头和结尾恰好有一个是B，这样有$B'$段空位

（3）开头和结尾都不是B，这样有$B+1$段空位

这三种情况仅仅是在空位的段数上有所区别，计算过程其实是一样的（计算答案时要将情况（2）的方案数$\times 2$）。

现在我们已经可以不用关心B了。设有$n$段空位，我们枚举$x_{0}$，很容易列出如下方程组 $$x_{1}+x_{-1}=n-x_{0} \\ x_{1}-x_{-1}=R'-G'$$ 解得 $$x_{1}=\frac{n-x0+R'-G'}{2} \\ x_{-1}=\frac{n-x0+G'-R'}{2}$$ 如果解得的$x_{1}$和$x_{-1}$不是整数，我们可以直接continue。现在我们确定每种空位的个数后，我们先要确定空位的顺序，其数量为$\frac{n!}{x0!\times x_{1}!\times x_{-1}!}$，这个可以通过$O(M)$预处理出$1$到$M$的阶乘及其逆元，然后$O(1)$求得。接下来我们要对空位进行补充，让它们合法。对于RGR...RG和GRG...GR，我们分别填上RG和GR；对于RGR...GR和GRG...RG，我们分别填上R和G。这样，我们剩余的元素个数为$R''=G''=R'-x_{0}-x_{1}=G'-x0-x_{-1}$。现在，我们还可以对每段空位进行补充，每次需要添加一个R和一个G。形式化的，我们需要求方程 $$\sum_{i=1}^{n}b_{i}=R’'(b_{i}\in \mathbb{N})$$ 解的个数。这是一个经典问题，设$a_{i}=b_{i}+1$，原方程可化为 $$\sum_{i=1}^{n}a_{i}=R''+n(a_{i}\in \mathbb{N}^{*})$$ 该方程可以理解为由$R''+n$个球，需要在$R''+n-1$个空中插入$n-1$个隔板把它们分成$n$份，故方案数为$\binom{R''+n-1}{n-1}$，这个也可以用预处理得到的阶乘及其逆元$O(1)$求得。

至此，问题得到了完美解决，时间复杂度为$O(M)$。

注意点

在计算过程中，$n,R',x_{1},R''$等变量可能变成负数，需要及时舍去。