首页 > 代码库 > 第6届—校赛 小明的骰子

第6届—校赛 小明的骰子

小明的骰子

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)
(2,2)(2,3)(2,4)(2,5)(2,6)
(3,3)(3,4)(3,5)(3,6)
(4,4)(4,5)(4,6)
(5,5)(5,6)
(6,6)
即,一共21种

来源


校赛的题目,当时没找到规律,现在总结一下:

用题目中的提示,打表  1,2,3,4,5,6   朝上时的种类数 。

当色子为 n 时,其中的重复情况,在前 n-1 只色子时已经排除了,在考虑第n中色子时,又会在 前  n-1 只色子的 同数字的个数 重复 所以要减去。


规律就是 第3只色子为例:

              21 - 6  = 15
              15 - 5  = 10
              10 - 4  = 6
               6 - 3 = 3
              3 - 2 = 1



当前列 减掉  同行前列的 部分色子数:
 

示例程序


#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int mod = 1000007;
using namespace std;

long long a[10][1010];
int main()
{
int i;
    memset(a,0,sizeof(a));
    for(i = 1;i<=6;i++)
        a[i][1] = 1;
    a[7][1] = 6;
    int l = 1,j;
    for(i = 2;i<=1010;i++)
    {
        a[1][i] = a[7][i-1];
      a[7][i] = a[1][i];
        for(l = 2;l<=6;l++)
        {
            a[l][i] = a[l-1][i]-a[l-1][i-1];
            a[7][i] += a[l][i];
        }
    }
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;

        cout<<a[7][n]%mod<<endl;
    }
    return 0;
}