题目意思很好懂,给你n个骰子、请问滚出数字为m的概率是多少?

这个很坑爹啊,开始想用母函数来搞,后来发现不对劲啊,n有100,开100次方早就是大数了,那怎么办,只能按照常规方法递推,然后还因为没考虑边界问题WA一次。心痛。


代码:

StatusAccepted
Time1ms
Length853
LangG++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=605;
int n, m, have, tot, up, down;
double dp[maxn], ans[maxn];
int main()
{
    while(~scanf("%d%d", &n, &m)){
        memset(ans, 0, sizeof(ans));
        for(int i=1;i<=6;i++)ans[i]=1.0/6;
        down=1;up=6;
        for(int i=1;i<n;i++){
            for(int j=down;j<=up;j++){
                for(int k=1;k<=6;k++){
                    dp[j+k]+=ans[j]*1.0/6;
                }
            }
            down++;up+=6;
            for(int j=down;j<=up;j++){
                ans[j]=dp[j];
                dp[j]=0;
            }
        }
        if(m>=n&&m<=n*6)
            printf("%.2lf\n", ans[m]*100);
        else printf("0.00\n");
    }
    return 0;
}