玲珑学院OJ 1091 Black and White【dp+前缀和】经典模型

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，要求不能有连续的a个颜色a出现，也不能有连续的b个颜色b出现。

问有多少种分配方式。

思路：

1、统计计数问题，考虑dp，设定dp【i】【2】，其中：

①dp【i】【0】表示长度为i的格子，以a颜色结尾的情况数。

②dp【i】【1】表示长度为i的格子，以b颜色结尾的情况数。

2、那么不难推出其状态转移方程：dp【i】【0】=Σdp【i-j】【1】（0<j<a）

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

但是直接转移时间复杂度爆炸，肯定是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);    }}