学步园

UVA_10759

    我们不妨把N个色子看成是依次投掷的，这样最多才6^N个状态，用long long是可以表示的，而我们又比较容易用DP求出不大于X的状态总数，这样计算完之后再约分一下即可。

#include<stdio.h>
#include<string.h>
int N, X;
long long int f[30][160];
long long int gcd(long long int x, long long int y)
{
return y == 0 ? x : gcd(y, x % y);
}
void solve()
{
int i, j, k, p;
long long int a, b, c;
    memset(f, 0, sizeof(f));
for(j = 1; j <= 6; j ++)
for(k = j + 1; k <= X; k ++)
            f[1][k] += 1;
for(i = 2; i <= N; i ++)
for(j = 1; j <= 6; j ++)
for(k = j + 2; k <= X; k ++)
                f[i][k] += f[i - 1][k - j];
    b = 1;
for(i = 1; i <= N; i ++)
        b *= 6;
    a = b - f[N][X];
    c = gcd(b, a);
    a /= c, b/= c;
if(a == 0)
        printf("0\n");
else if(b == 1)
        printf("1\n");
else
        printf("%lld/%lld\n", a, b);
}
int main()
{
for(;;)
    {
        scanf("%d%d", &N, &X);
if(!N && !X)
break;
        solve();
    }
return 0;
}