首页 > 代码库 > 西南民大oj（递推）
西南民大oj（递推）
我的数学不可能那么难推
时间限制(普通/Java) : 3000 MS/ 9000 MS 运行内存限制 : 65536 KByte
总提交 : 49 测试通过 : 24
View Code
总提交 : 49 测试通过 : 24
描述
没什么题出了，怎么办呀~
好吧，百度一道去。
于是此题横空出世，只为开心。
小明喜欢下棋，一日他闲来无聊，将黑白棋子排成一长条观察，发现黑色混在一起好难看啊。
随即想到，黑与黑子不相邻，摆放成一长条，有多少种可能乎？！
输入
多组测试数据，（大概1w组吧
）
第一行，棋子的总数 n （0<n<=1000000）
输出
只有一行，保证黑子与黑子不相邻，棋子摆放的所有情况数目取模1000000007后的结果。
样例输入
1
100
样例输出
2
470199269
分析：设a[i]为i个棋子的总种数，b[i]为以白棋结尾的总种数，c[i]为以黑棋为结尾的总种数。则有a[i]=b[i]+c[i],b[i]=a[i-1],c[i]=b[i-1];
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 1000010using namespace std;int a[N],b[N],c[N];void init(){ a[1]=2;b[1]=1;c[1]=1; for(int i=2;i<=1000000;i++) { b[i]=a[i-1];c[i]=b[i-1]; a[i]=b[i]+c[i]; a[i]%=mod; }}int main(){ int n; init(); while(scanf("%d",&n)>0) { printf("%d",a[n]); }}
西南民大oj（递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。