其实只是因为要给同学出题找的这道题， 不过在网上看到的一些题解似乎对一个细节并没有写得清楚，在此写个题解 没想到之前太早发，又碰上爱学习的神犇wx同学…

---

题目

题意

有GRP三个军种，G最多连续M个，R最少连续K个，求安排N个的方案数

输入

有多个测试用例(反正跑得过)。对于每种情况，存在包含3个整数N（0

输出

每种情况下一行，应输出mod 1000000007后的结果

输入样例

3 2 2

输出样例

5

说明

将驻军，侦察机关和军警视为G，R和P. 合理安排有：GGG，GGR，GGP，RGG，PGG。

---

题解

设

因要判断不同军种的连续性问题，需要开两维，一维表示当前是第i个，一维表示当前军种为j

达成共识

首先为了方便用同一个表示方法表示，当然最好是将最多最少连续同一：将最多连续转化为最少连续或将最少连续转化为最多连续 上面设的部分中还没说表示什么，比较可以发现将最少连续转化为最多连续是最方便的 而如何将最少连续转化为最多连续呢？ 类似组合数学的，可以用最多连续N个减去最多连续M-1个表示 用u，v表示每次计算时G最多连续u个，R最多连续v个 答案即为两次递推答案相减，v不变，u一次为N，一次为M-1

分三个军种讨论

j表示P时

无需考虑前面情况，全部加起来即可

j表示G时

i <=u时

不可能多过连续要求，全部加起来即可

i == u+1时

有一种情况正好超过连续要求，全部加起来减去1即可

i>u+1时

我就是说这个细节应该用更好的方式理解 当然会有多种情况超过连续要求 这个时候网上的题解是类似于

//减去i-1~i-u-1全是G的情况

其实我觉得可以跟之前最少连续转最多连续一样的方法理解 为了不出现超过连续要求的情况， 逆向思考这种情况即为 至少有i-u个其他兵种在前，于是 每一个其他兵种这样的情况自然为 (fi−1,x−fi−u−1,x) ，有两种其他兵种，与当前兵种正常加起来即可

j表示R时

类似可推出

---

代码

#include <cstdio> #include <cstring> const int mod = 1000000007, maxn = 1e6 + 100; typedef long long ll; ll dp[maxn][3]; //0 G, 1 R, 2 P int n, m, k; ll work(int u, int v){ dp[0][0] = dp[0][1] = 0, dp[0][2] = 1; ll res; for (int i = 1, j = 0; i <= n; ++i, ++j){ dp[i][0] = dp[i][1] = dp[i][2] = res = ((dp[j][0] + dp[j][1]) % mod + dp[j][2]) % mod; if (i == u + 1) dp[i][0] = res - 1; if (i > u + 1) dp[i][0] = res - dp[j - u][1] - dp[j - u][2]; if (i == v + 1) dp[i][1] = res - 1; if (i > v + 1) dp[i][1] = res - dp[j - v][0] - dp[j - v][2]; } return ((dp[n][0] + dp[n][1]) % mod + dp[n][2]) % mod; } int main (){ //freopen ("titans.in", "r", stdin); //freopen ("titans.out", "w", stdout); ll ans; while(~scanf ("%d%d%d", &n, &m, &k)){ printf ("%lld\n", ((work(n, k) - work(m - 1, k)) % mod + mod) % mod); } return 0; }