NC23413 小A买彩票

题解：这个题既然我们要求他不亏本的概率，那么我们就需要找出所有的情况和不亏本的情况。
然后用不亏本的情况，也就是说总钱数要大于等于3*n的情况数来除以总的情况数。
接下来就可以用dp的方法做题了。
dp[i][j]代表前i个彩票中奖的钱数为j的方案数。
然后就相当于是一个递推式。

dp[i][j]+=dp[i-1][j-k]（前提：j大于等于k，k可以取1，2，3，4）
为什么这么写呢，是因为我要买第i张彩票了，中的奖金为k元，那么我们的总奖金就是j-k+k元，可以从前一张彩票的价格推过来。

最后一个问题，最后的分数他有可能不是最简形式，这样的话我们就可以给他化简，找出两者的最大公约数，然后同时除以这个最大公约数即可。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
ll dp[50][200];

int main()
{
    ll n;
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i*4;j++){
            for(int k=1;k<=4;k++){
                if(j>=k){
                    dp[i][j]+=dp[i-1][j-k];
                    //printf("前%d个彩票，多少%d钱的 方案%d\n",i,j,dp[i][j]);
                }
            }
        }
    }
    ll ans1=0,ans2=0;
    for(int i=n;i<=n*4;i++){
        if(i>=n*3) ans1+=dp[n][i];
        ans2+=dp[n][i];
    }
    ll gcd=__gcd(ans1,ans2);
    printf("%lld/%lld",ans1/gcd,ans2/gcd);
    return 0;
}