lightoj 1064 Throwing Dice

时间：2023-12-11 19:49:50

　　题意：给你n个骰子，求n个骰子的和不小于x的概率。

　　刚开始想每给一组数就计算一次~~太笨了- -，看了别人的代码，用dp，而且是一次就初始化完成，每次取对应的数据就行了。WA了好多次啊，首先不明白的就是：

for(int i=;i<=;i++) for(int j=i*;j>=;j--) dp[i][j]+=dp[i][j+];

　　这段代码不清楚干什么用的，想清楚没？

　　刚开始求的dp[i][j]表示的是前 i 个骰子掷出总和为 j 的概率 ，题意让求总和不小于 j 的概率，所以把大于 j 的要加上。

　　然后输出的又WA了好几次~~

　　有概率为0和1的情况，就不能输出分数形式。

#include<stdio.h>

#include<string.h>

#define N 30

#define LL long long

LL dp[N][N*],p[N];

void Init()

{

    memset(dp,,sizeof(dp));

    p[]=;

    for(int i=;i<=;i++)  p[i]=p[i-]*;

    for(int i=;i<=;i++)   dp[][i]=;

    for(int i=;i<=;i++)

        for(int j=i;j<=i*;j++)

            for(int k=;k<=;k++)

                if((j-k)>=i-)

                    dp[i][j]+=dp[i-][j-k];

    for(int i=;i<=;i++) for(int j=i*;j>=;j--) dp[i][j]+=dp[i][j+];

}

LL Gcd(LL a,LL b)

{

    return b?Gcd(b,a%b):a;

}

int main()

{

    Init();

    int T,cas=;

    int n,x;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&x);

        LL a=p[n];

        LL b=dp[n][x];

        LL yu = Gcd(a,b);

        if(a/yu==)    printf("Case %d: %lld\n",cas++,b/yu);

        else    printf("Case %d: %lld/%lld\n",cas++,b/yu,a/yu);

    }

    return ;

}

相关文章