骰子游戏

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    int n, x;
    scanf("%d%d", &n, &x);
    if(n>=x)
        puts("1");
    else if(6*n < x)
        puts("0");
    else{
        long dp[25][151]={0};
        for(int i=1;i<=6;i++)
            dp[1][i] = 1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=x;j++)
                for(int k=1;k<=6;k++){
                    if(j<k)
                        break;
                    dp[i][j] += dp[i-1][j-k];
                }
        long s=0, a, b=pow(6, n), t;
        for(int i=1;i<x;i++)
            s += dp[n][i];
        a = b - s;
        t = __gcd(a, b);
        printf("%ld/%ld\n", a/t, b/t);
    }
    return 0;
}

//动态规划，注释写的很详细了，建议把dp输出看一看
#include<iostream>
#include<cmath>
using namespace std;
long long int dp[25][155];    //dp[i][j] 表示投掷了i个骰子，分数为j的方案种数，这里要用long long int，不然n,x大了后面会溢出 
long func(long a,long b){        //求最大公约数 
    long temp;
    while(b>0){
        temp=a%b;
        a=b;
        b=temp;
    }
    return a;
}
int main(){
    int n,x,i,j;
    cin>>n>>x;
    if(n>=x)        //所有骰子都投了1也能到达x分，怎么投都满足条件了 
        cout<<1;
    else if(6*n<x)    //所有骰子都投了6还是达不到x分 
        cout<<0;
    else{
        for(i=1;i<=6;i++)
            dp[1][i]=1;            //只投一个骰子，分数为i的方案数为1 
        for(i=1;i<=n;i++){        //从投一个骰子到n个骰子 
            for(j=1;j<=x;j++){        
                for(int k=1;k<=6;k++){    //骰子只有1-6 
                    if(j-k<0)        //如果j-k<0就没有必要继续比较了  对后面的k,j-k肯定都是<0的了 
                        break;
                    dp[i][j]+=dp[i-1][j-k];    //投了i个骰子，总得分为j的方案数=投了i-1个骰子，得分为j-1,j-2,...,j-k（当然前提要j-k>=0,因为不可能投了i-1个骰子得了负分） 
                }
            }
        }
        long long int sum=0,fenmu=pow(6,n);        //分母=6^n 
        for(i=1;i<=x-1;i++)     
            sum+=dp[n][i];                //将得分达不到x的方案数加起来 
        long gcd=func(fenmu-sum,fenmu);        //分子=6^n-sum,求分母分子的最大公约数 
        cout<<(fenmu-sum)/gcd<<"/"<<fenmu/gcd;        //输出最简分数 
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * https://blog.csdn.net/qq_32767041/article/details/86420299
 *
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), x = Integer.parseInt(strs[1]);

        //骰子最大面值
        int diceMaxVal = 6;
        //count[][n]: 点数和为n出现的次数
        long[][] count = new long[2][diceMaxVal * n + 1];

        int flag = 0;
        for (int i = 1; i <= diceMaxVal; i++) count[flag][i] = 1;

        for (int k = 2; k <= n; k++) {
            //有k个骰子时，最小点数和为k，不存在出现点数和小于k的情况
            for (int i = 1; i < k; i++) count[1 - flag][i] = 0;

            for (int i = k; i <= diceMaxVal * k; i++) {
                count[1 - flag][i] = 0;
                for (int j = 1; j < i && j <= diceMaxVal; j++) {
                    count[1 - flag][i] += count[flag][i - j];
                }
            }

            //在下一轮中，交换两个数组，通过改变flag实现
            flag = 1 - flag;
        }

        long sum = 0, total = (long) Math.pow(diceMaxVal, n);
        for (int i = x; i <= diceMaxVal * n; i++) sum += count[flag][i];

        long  maxDivisor = gcd(total, sum);
        if (sum == 0) System.out.println(0);
        else if (sum == total) System.out.println(1);
        else System.out.println((sum / maxDivisor) + "/" + (total / maxDivisor));
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

可用动态规划加旋转数组实现。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = 0, x = 0;
        try {
            String[] str = br.readLine().split(" ");
            n = Integer.parseInt(str[0]);
            x = Integer.parseInt(str[1]);
        } catch (IOException e) {
            e.printStackTrace();
        }
        final int maxValue = 6; 
        final int sum = maxValue * n;
        long[][] prb = new long[2][sum + 1];
        for (int i = 0; i <= sum; i++) {
            prb[0][i] = 0;
            prb[1][i] = 0;
        } //初始化
        int flag = 0;
        for (int i = 1; i <= maxValue; i++) {
            prb[flag][i] = 1;
        }  //扔出1个骰子的概率
        for (int i = 2; i <= n; i++) {  //i代表骰子数
            for (int j = 0; j <= i; j++)
                prb[1 - flag][j] = 0; //数组prb[1-flg]保存新增骰子时的概率，最小值为1*i
            for (int j = i; j <= sum; j++) {  //j代表当前的和
                prb[1 - flag][j] = 0;
                for (int k = 1; k <= maxValue && k <= j; k++) {
                    prb[1 - flag][j] += prb[flag][j - k];//k代表当抛出的值，当抛出k时，当前和为j时的概率等于之前j-1,j-2...j-k的和
                }
            }
            flag = 1 - flag;
        }
        long tsum = new Double(Math.pow(maxValue, n)).longValue();  //总数
        long sumi = 0;  //大于x的数
        for (int i = x; i <= sum; i++) {
            sumi += prb[flag][i];
        }
        if (sumi == 0)
            System.out.println(0);
        else if(sumi==tsum)
            System.out.println(1);
        else {
            long maxD = maxDiv(sumi, tsum);
            String res = Long.toString(sumi / maxD) + "/" + Long.toString(tsum / maxD);
            System.out.println(res);
        }
    }

    public static long maxDiv(long a, long b) {
        return b == 0 ? a : maxDiv(b, a % b);
    }

}

/*
*在网上看了一下思路，特意整理了一下
*dp思想，dp[i][j] 表示i个筛子可以产生j一共有多少种结果
*dp[1][j]=1(j=1~6)
*dp[i][i]=1,dp[i][6*i]=1
*dp[i][j]+=dp[i-1][j-k](k=1~6)，表示i个筛子产生的结果只能1~6，然后加上i-1个产生结果即可
*/
#include<iostream>
#include<random>
using namespace std;
typedef long long ll;
ll dp[30][150];///注意这里一定要用long long 否则会溢出
ll gcd(ll x, ll y)
{
    if (x%y == 0) return y;
    else return (gcd(y, x%y));
}
int main()
{
    int n,x;
    while(cin>>n>>x){
        if(x==n){ ///概率为1的情况
            cout<<1<<endl;
            continue;
        }else if(x<n||x>n*6){///概率为0的情况
            cout<<0<<endl;
            continue;
        }else{
            ///初始化
            for(int i=0;i<=n;i++){
                for(int j=0;j<=6*i;j++){
                    dp[i][j]=0;
                }
            }
            for(int i=1;i<=n;i++){ ///n个筛子，循环n次
                for(int j=i;j<=6*i;j++){
                    if(i==1||i==j||j==6*i){
                        dp[i][j]=1;
                    }else{
                        for(int k=1;k<=6;k++){
                            if(j-k>=i-1)///i-1个筛子的结果范围一定是大于等于i-1的
                                dp[i][j]+=dp[i-1][j-k];
                        }
                    }
                }
            }
        }
        ll sum=0;
        ll p=0;
        for(int i=n;i<=6*n;i++){
            if(i>=x) p+=dp[n][i];
            sum+=dp[n][i];
        }
        ll c=gcd(p,sum);
        p/=c;
        sum/=c;
        cout<<p<<"/"<<sum<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int g_maxvalue = 6;
long long gcd(long long x, long long  y)
{
    if (x%y == 0) return y;
    else return (gcd(y, x%y));
}
int main()
{
    int n, x;
    while (cin >> n >> x)
    {
        long long *pro[2];
        pro[0] = new long long[g_maxvalue*n + 1];
        pro[1] = new long long[g_maxvalue*n + 1];
        for (int i = 0; i<g_maxvalue*n + 1; ++i)
        {
            pro[0][i] = 0;
            pro[1][i] = 0;
        }
        int flag = 0;
        for (int i = 1; i<=g_maxvalue; i++)
            pro[flag][i] = 1;
        for (int k = 2; k<=n; k++)
        {
            for (int i = 0; i<k; i++)
                pro[1 - flag][i] = 0;
            for (int i = k; i<=g_maxvalue*k; i++)
            {
                pro[1 - flag][i] = 0;
                for (int j = 1; j <= i&&j <= g_maxvalue; j++)
                    pro[1 - flag][i] += pro[flag][i - j];
            }
            flag = 1 - flag;
        }
        long long cnt = 0;
        for (int i = n; i<=g_maxvalue*n; i++)
        {
            if (i >= x) cnt += pro[flag][i];
        }
        
        long long total = pow(g_maxvalue, n);
        delete[] pro[0];
        delete[] pro[1];
        if (cnt == 0) cout << "0" << endl;
        else if (cnt == total) cout << "1" << endl;
        else{
            long long gcdnum = gcd(cnt, total);
            cout << cnt/gcdnum<< "/" << total/gcdnum << endl;
        }
    }
    return 0;
}

import java.math.BigInteger;
import java.util.*;

public class Main {
    private static final int N_MAX = 25 + 5;
    private static final int X_MAX = 150 + 5;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt();
        long[][] dp = new long[N_MAX][X_MAX];
        dp[0][0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=x; j++) {
                for (int k=1; k<=6 && j+k<=x; k++) {
                    dp[i][j+k] += dp[i-1][j];
                }
            }
        }
        long ans = 0;
        for (int i=0; i<x; i++) {
            ans += dp[n][i];
        }
        long fenmu = (long)Math.pow(6, n);
        long[] result = simplify(fenmu - ans, fenmu);
        if (result[0] == 1 && result[1] == 1) {
            System.out.println(1);
        }
        else if (result[0] == 0) {
            System.out.println(0);
        }
        else {
            System.out.printf("%d/%d", result[0], result[1]);
        }
    }

    private static long[] simplify(long fenzi, long fenmu) {
        long gcd = BigInteger.valueOf(fenzi).gcd(BigInteger.valueOf(fenmu)).longValue();
        return new long[]{fenzi / gcd, fenmu / gcd};
    }
}

import java.io.IOException;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        long p = 1;
        for (int i = 1; i <= n; i++) {
            p *= 6;
        }
        if(x > 6 * n){
            System.out.println(0);
            return;
        }
        long[][] dp = new long[n + 1][x];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = i; j < x; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j >= k) {
                        dp[i][j] += dp[i - 1][j - k];
                    }
                }
            }
        }
        long s = 0;
        for (int i = 0; i < x; i++) {
            s += dp[n][i];
        }
        s = p - s;
        long gcd = gcd(s, p);
        s /= gcd;
        p /= gcd;
        if (p == 1) {
            System.out.println(1);
        } else {
            System.out.println(s + "/" + p);
        }


    }


    public static long gcd(long m, long n) {
        if (m < n) {
            return gcd(n, m);
        }
        long r = m % n;
        while (r != 0) {
            m = n;
            n = r;
            r = m % n;
        }
        return n;
    }
}

import java.io.*;
import java.lang.*;

public class Main {
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(
            new InputStreamReader(System.in)));
    private static int nextInt() {
        try {
            st.nextToken();
            return (int)st.nval;
        }catch(IOException e) {
            throw new RuntimeException(e);
        }
    }
    public static void main(String[] arg) {
        int n = nextInt();
        int x = nextInt();
        if(n >= x) {
            System.out.println("1");
            return;
        }
        if(x > 6 * n) {
            System.out.println("0");
            return;
        }
        long[] dp = new long[x + 1];//错误二：溢出
        for(int i = 1; i <= 6; i++) {
            dp[i] = 1;
        }
        for(int i = 1; i < n ; i++) {
            for(int j = x; j > i; j--) {
                dp[j] = 0;//关键
                for(int m = 1; m <= 6; m++) {
                    if(j - m >= i) {
                        dp[j] += dp[j - m];
                    }
                }
            }
        }
        long sum = (long)Math.pow(6,n);
        long subtract = 0;
        for(int i = n; i < x; i++) {
            subtract += dp[i];
        }
        long divisor = biggestCommonDivisor(sum, sum - subtract);
        System.out.println((sum - subtract)/divisor + "/" + sum/divisor);
    }
    public static long biggestCommonDivisor(long a, long b) {
        while(a % b != 0) {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        String[] ags = rd.readLine().split(" ");
        int n = Integer.parseInt(ags[0]);
        int x = Integer.parseInt(ags[1]);
        if(x < n || n < 1 || (n == 1 && x >= 6)){
            System.out.println(0);
            return ;
        }
        long[] res = twoSum(n);
        long sum = 0;
        long dis = (long)Math.pow(6, n);
        
        for(int i = x - n; i < res.length; i++){
            sum += res[i];
        }
        long b = gy(dis, sum);        
        if(b == 0)
            System.out.println(0);
        if(dis == sum){
            System.out.println(1);
        }
        else
            System.out.print(sum/b + "/" + dis/b);
        
    }
    public static long[] twoSum(int n) {
        long[] a = new long[5 * n + 1];
        for(int i = 0; i < 6; i++){
            a[i] = 1;
        }
        if(n == 1)
            return a;
        for(int i = 2; i <= n; i++){
            for(int j = 6 * i; j >= i; --j){
                long sum = 0;
                for(int k = 1; k <= 6; k++){
                    if((j-k-(i-1)) < 0){
                        break;
                    }
                    sum+=a[j-k-(i-1)];
                }
                a[j-i] = sum;
            }
        }
        return a;
    }
    private static long gy(long a, long b) {
        return b == 0 ? a : gy(b, a % b);
    }
}

一个容量为n的背包，n个价值为1-6的物品，价值为6-6*n，找出价值大于等于x的种数和，除6^n即可，f(n,x) = f(n-1,x-1)+f(n-1,x-2)+f(n-1,x-3)+f(n-1,x-4)+f(n-1,x-5)+f(n-1,x-6)，当x-i>=0时。