小A买彩票题目题解

题目描述：

3元买一张彩票，买一张彩票得到1，2，3，4元的概率相等。问买n次，不亏的概率多少，输出最简分数形式。

思路：

由题意我们得，这一次买彩票新出现的情况是由上次买彩票的情况分别加上1，2，3，4元得到的。于是我们可以想到使用DP来解决这道题目，状态转移方程是：

f[i][j]+=f[i-1][j-k];

其中，i 代表当前是第 i 次买彩票，j代表这次买完之后的钱数，k代表这次得到的钱。
于是，我们对彩票数由 1 ~ n 遍历，j由 0 ~ i*4 遍历，k由1到4遍历，然后把所有第n次得钱不亏的加起来，就组成了我们结果的分子。而分母很好求，就是4的n次方。

for(int i=1;i<=n;i++) {
        for(int j=0;j<=i*4;j++) {
            for(int k=1;k<=4;k++) {
                if(j>=k)//一定不要忘了
                    f[i][j]+=f[i-1][j-k];
            }
        }
    }

由于他要求的是最简形式，所以我们要对分子分母求最大公因数，然后同除它，就可以得到结果。

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

完整代码：

#include<iostream>
#include<cmath>
using namespace std;

long long f[35][130];
long long gcd(long long a,long long b) {
    return b==0?a:gcd(b,a%b);
}

int main() {
    int n;
    cin>>n;
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=i*4;j++) {
            for(int k=1;k<=4;k++) {
                if(j>=k)//一定不要忘了
                    f[i][j]+=f[i-1][j-k];
            }
        }
    }

    long long cnt=0;
    for(int i=3*n;i<=4*n;i++) {
        cnt+=f[n][i];
    }
    long long sum=pow(4,n);
    if(cnt==0) {
        puts("0/1");
    }
    else {
        long long div=gcd(cnt,sum);
        cnt/=div;
        sum/=div;
        printf("%lld/%lld\n",cnt,sum);
    }
    return 0;
}