首页 > 代码库 > 涂色游戏
涂色游戏
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。