Time Limit：4s Memory Limit：128MByte

Submissions：243Solved：75

Constroy likes the game called Reversi. He has a long paper tape with nn grids, where each grid should fill by one black chess or one white chess exactly. Constroydislikes the situation with aa consecutive black chesses or bb consecutive white chesses, so he intends to know how many situaions satisfy his PReference.

The answer may be so large, but you only need to give the answer modulo (109+7)(109+7).

一共有N個格子，對于這N個格子來講，要么涂成顏色a，要么涂成顏色b，要求不能有連續(xù)的a個顏色a出現(xiàn)，也不能有連續(xù)的b個顏色b出現(xiàn)。

問有多少種分配方式。

思路：

1、統(tǒng)計計數(shù)問題，考慮dp，設(shè)定dp【i】【2】，其中：

①dp【i】【0】表示長度為i的格子，以a顏色結(jié)尾的情況數(shù)。

②dp【i】【1】表示長度為i的格子，以b顏色結(jié)尾的情況數(shù)。

2、那么不難推出其狀態(tài)轉(zhuǎn)移方程：dp【i】【0】=Σdp【i-j】【1】（0<j<a）

dp【i】【1】=Σdp【i-j】【0】  (0<j<b)

但是直接轉(zhuǎn)移時間復(fù)雜度爆炸，肯定是TLE的.那么考慮過程維護一個前綴和即可。

Ac代碼：

#include<stdio.h>#include<string.h>using namespace std;#define mod 1000000007int dp[1000050][2];int sum[1000050][2];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int a,b,n;        scanf("%d%d%d",&a,&b,&n);        memset(dp,0,sizeof(dp));        memset(sum,0,sizeof(sum));        dp[0][0]=1,dp[0][1]=1;        sum[0][0]=1,sum[0][1]=1;        for(int i=1;i<=n;i++)        {            if(i<a)dp[i][0]=(dp[i][0]+sum[i-1][1])%mod;            else            {                dp[i][0]=(dp[i][0]+sum[i-1][1]-sum[i-a][1]+mod)%mod;            }            if(i<b)dp[i][1]+=sum[i-1][0];            else            {                dp[i][1]=(dp[i][1]+sum[i-1][0]-sum[i-b][0]+mod)%mod;            }            sum[i][0]=(sum[i-1][0]+dp[i][0])%mod;            sum[i][1]=(sum[i-1][1]+dp[i][1])%mod;        }        int output=(dp[n][0]+dp[n][1])%mod;        printf("%d/n",(output+mod)%mod);    }}