首页 > 代码库 > 涂色游戏

涂色游戏

2024-07-09 11:12:20   215人阅读

Description

在一个1*N的格子上，每个格子可以选择涂成红色或蓝色。 求至少 M 个连续为红色的方案数。

Input

多组输入，每组输入包含两个整数M和N  (0<N,M<100000)

Output

输出存在至少连续M个为红色的方案数，对1000000007取模

Sample Input

3 4

Sample Output

3
这道题有点意思，基本就是核电站问题的翻版
基本思路就是，还是和核电站一样，要考虑前几个格子避免连续n个红格子的思路
嗯，忘了刚才那句吧，我再说一遍
f[i]请参见核电站对f数组的定义
而q[i]就是这次前i个 （里面至少 M 个连续为红色）的方案数
 
q[i]=q[i-1]*2(这里就是指在第i个涂红还是不涂红)+f[i-m-1](考虑到i-m+1到i全涂红的方案数)
#include<iostream>#include <stdio.h>  #include <math.h>#include<stdio.h>#include<string.h>  using namespace std; const int MOD=1e9+7;int main(){     long long  f[100000];int i,n,m;     long long  g[100000];    int number;    while(scanf("%d%d",&m,&n)!=EOF)    {	 memset(f,0,sizeof(f));		 memset(g, 0,sizeof(g));		f[0]=1;	    for(i=1;i<=n;i++)	    {	    	 if(i<m)			 {			 	f[i]=2*f[i-1];			 	f[i]%=MOD;			 	g[i]=0;			 }   		 	 if(i==m)			 {				 	f[i]=2*f[i-1]-1;				 	f[i]%=MOD;				 	g[i]=1; 			 }    	if(i>m)		 {			 f[i]=2*f[i-1]-f[i-m-1]+MOD;		 	f[i]=f[i]%MOD;			g[i]=2*g[i-1]+f[i-m-1]+MOD;			g[i]=g[i]%MOD;					 		 }		 	} 	 for(i=1;i<=n;i++)    {    	printf(" g[%d]=%d  f[%d]=%d \n",i,g[i],i,f[i]);	}    cout<<g[n]%1000000007<<endl;//	cout<<" "<<m+n<<endl;	}        return 0;    }

　　


联系
我们