小A买彩票

题意

买一张彩票3元，等概率得到1,2,3,4元，买张彩票，问不亏的概率。

分析

我们可以利用不亏的方案数除以总的方案数，得到不亏的概率。
定义表示买了张，共得到元的方案数。
显然，我们只需要枚举第次得到多少元就行了。
然后注意的情况就好了。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 32;
const int M = 1e9+7;
int n,m,k,ok;

int dp[maxn][125];

signed main()
{
    cin>>n;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= 4; j++)        //第i次得到j元
        {
            for(int k = 0; k <= 120; k++)
            {
                dp[i][j+k] += dp[i-1][k];
            }
        }
    }
    int res = 0,ans = 0;
    for(int j = 0; j <= 120; j++)
    {
        res += dp[n][j];
        if(j >= 3*n) ans += dp[n][j];
    }
    int gcd = __gcd(res,ans);
    if(gcd)
    {
        ans /= gcd;
        res /= gcd;
    }
    cout<<ans<<'/'<<res<<endl;
    return 0;
}