首页 > 代码库 > 小明的骰子（递推）
小明的骰子（递推）
小明的骰子
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描写叙述
众所周知，小明很喜欢玩骰子。一天，小芳问小明一个问题。一次性抛n个骰子，一共能抛出几种结果？
小明不想让小芳认为自己回答不上来，所以小明来求助于你。你一定要帮帮小明。
输入
首先输入一个整数T，代表有T组数据。
接下来的T行，每行输入一个整数n，代表有n个骰子。（0<n<=1000）
注：1，每一个骰子有6个面。
2，每一个骰子都是同样的。所以（1，1，2）和（1，2，1）是同样的结果。
输出
输出一次性抛n个骰子，一共能抛出几种结果。由于结果有可能非常大，所以输出的结果要对1000007取余。
演示样例输入
2 1 2
演示样例输出
6 21
提示
假设仅仅抛一次骰子，骰子有6个面。所以一共能够抛出6种可能性。
假设一次性抛2个骰子，可能的结果有下面几种：
（1，1）（1，2）（1，3）（1，4）（1，5）（1，6） 6
（2，2）（2，3）（2，4）（2，5）（2，6） 5
（3，3）（3，4）（3，5）（3，6） 4
（4，4）（4，5）（4，6） 3
（5，5）（5，6） 2
（6，6） 1
即，一共21种 合计21
校赛的时候的一道题，那个时候我还不知道递推为何物。。
将6种骰子开头的总类打表 即f[1][j]--f[6][j] （j代表骰子的数目）f[7][j]为f[1][j]--f[6][j]的和 即骰子数为 j 时的答案
规律就是以1开头骰子即f[1][j] 其值等于f[7][j-1] 而f[i][j]=f[i-1][j]-f[i-1][j-1] (i>=2) 规律在纸上找的，这里我也没办法打出来了。。找起来的话不算难 写出前4种情况差点儿相同就能看出来了
#include <iostream> //小明的骰子--递推
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
long long f[10][1010];
const int MOD=1000007;
int main()
{
int i,j,t,n;
for(i=1;i<=6;i++)
f[i][1]=1;
f[7][1]=6;
for(j=2;j<=1010;j++)
{
f[1][j]=f[7][j-1];
f[7][j]=f[1][j];
for(i=2;i<=6;i++)
{
f[i][j]=f[i-1][j]-f[i-1][j-1];
f[7][j]+=f[i][j];
}
}
cin>>t;
while(t--)
{
cin>>n;
cout<<f[7][n]%MOD<<endl;
}
return 0;
}小明的骰子（递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。