小明的骰子(递推)

小明的骰子

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;
}
时间: 09-23

小明的骰子(递推)的相关文章

小明的骰子--递推练习

小明的骰子 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 众所周知,小明非常喜欢玩骰子.一天,小芳问小明一个问题.一次性抛n个骰子,一共能抛出几种结果? 小明不想让小芳觉得自己回答不上来,所以小明来求助于你.你一定要帮帮小明. 输入 首先输入一个整数T,代表有T组数据. 接下来的T行,每行输入一个整数n,代表有n个骰子.(0<n<=1000) 注:1,每个骰子有6个面. 2,每个骰子都是相同的.所以(1,1,2)和(1,2

18025 小明的密码

18025 小明的密码 时间限制:4000MS  内存限制:65535K提交次数:0 通过次数:0 题型: 编程题   语言: G++;GCC Description 小明的密码由N(1<=N<=12)个数字构成,每个数字都可以是0至9中任意一个数字,但小明的密码还有 一个特点就是密码中连续的M(1<=M<=4)个数字的和是质数,现给定M和N,求满足条件的密码共有多少 个? 输入格式 第1行是T,case数量,此后T行,每行两个数,N和M 输出格式 每个case输出一个满足条件的密

scauoj 18025 小明的密码 数位DP

18025 小明的密码 时间限制:4000MS  内存限制:65535K提交次数:0 通过次数:0 题型: 编程题   语言: G++;GCC Description 小明的密码由N(1<=N<=12)个数字构成,每个数字都可以是0至9中任意一个数字,但小明的密码还有 一个特点就是密码中连续的M(1<=M<=4)个数字的和是质数,现给定M和N,求满足条件的密码共有多少 个? 输入格式 第1行是T,case数量,此后T行,每行两个数,N和M 输出格式 每个case输出一个满足条件的密

11.爱吃皮蛋的小明(斐波那契数列)

爱吃皮蛋的小明(斐波那契数列) 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题解 题目描述 Description 小明特别爱吃蛋,特别是皮蛋.他一次可以吃一个蛋或者两个蛋(整个吞下去),而且他喜欢吃得有花样,他想知道对于一定蛋的数量,有几种不同的吃法. 输入描述 Input Description 一行一个整数N,表示皮蛋的数量 输出描述 Output Description 一行一个整数sum,表示吃法总数 样例输入 Sample Input 3 样例

hdu 1207 汉诺塔II (DP+递推)

汉诺塔II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4529    Accepted Submission(s): 2231 Problem Description 经典的汉诺塔问题经常作为一个递归的经典例题存在.可能有人并不知道汉诺塔问题的典故.汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往

hdu 1267 递推

下沙的沙子有几粒? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4326    Accepted Submission(s): 2268 Problem Description 2005年11月份,我们学校参加了ACM/ICPC 亚洲赛区成都站的比赛,在这里,我们获得了历史性的突破,尽管只是一枚铜牌,但获奖那一刻的激动,也许将永远铭刻

【66测试20161115】【树】【DP_LIS】【SPFA】【同余最短路】【递推】【矩阵快速幂】

还有3天,今天考试又崩了.状态还没有调整过来... 第一题:小L的二叉树 勤奋又善于思考的小L接触了信息学竞赛,开始的学习十分顺利.但是,小L对数据结构的掌握实在十分渣渣.所以,小L当时卡在了二叉树. 在计算机科学中,二叉树是每个结点最多有两个子结点的有序树.通常子结点被称作“左孩子”和“右孩子”.二叉树被用作二叉搜索树和二叉堆.随后他又和他人讨论起了二叉搜索树.什么是二叉搜索树呢?二叉搜索树首先是一棵二叉树.设key[p]表示结点p上的数值.对于其中的每个结点p,若其存在左孩子lch,则key

01python算法之递推

递推 1什么是递推?:根据已有节点的值,以及规律推出之后节点的值 2为什么要用递推:简单的解决有规矩事件 3怎么用?: 我们举个经典的例子: 如果1对兔子每月能生1对小兔子,而每对小兔在它出生后的第3个月就可以生1对小兔子,如果从1对初生的小兔子开始,1年后能繁殖多少兔子? def my1(max): a ,b,c ,i= 1,0,0 0 while i<max: c = c+b b = a a = c print a+b+c i+=1 方法:我们可以把兔子分为1个月大的,2个月大的,3个月大的

HDU 5459 Jesus Is Here (递推)

有点麻烦的递推,看的时候请耐心,递推的时候不要有嵌套,向小的问题方向分解,然后注意边界. 字符串的递推式为 定义f为Si中的总长度 首先可以得到 然后考虑Si-2和Si-1之间的组合 为了得到小的问题,进行拆分 为了以后表示的方便和逻辑上的清晰,把Si~Si之间的组合总长度定义出来 因为这里的si-2和si-2的中间还有一段Si-3 所以其组合总长度就可以表示为 Ci表示Si中cff出现的次数,Li表示Si的长度 定义一个函数ccl 最后还剩下一个部分Si-2和Si-3 定义 至此,总方案已经可