Thinking Process

总方案数是$4^{n}4^n$，可行的方案的要求是中奖金额$\ge 3\ast n\backslash ge3*\; n$，最后做一个约分即可。

状态方程

DEFINATION
f[i][j]:买了i张彩票赚了j元的方案数
f[0][0] = 1
EQUATION
f[i][j] += f[i - 1][j - k] k$\subset \backslash subset\{\}${1,2,3,4}

Code

#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;

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

int n;
ll f[40][200];

int main () {
    cin >> n;
    f[0][0] = 1;
    for(int i = 1;i <= n; i ++) {
        for(int j = 0;j <= 4 * i; j ++ ) {
            if(j >= 1) f[i][j] += f[i - 1][j - 1];
            if(j >= 2) f[i][j] += f[i - 1][j - 2];
            if(j >= 3) f[i][j] += f[i - 1][j - 3];
            if(j >= 4) f[i][j] += f[i - 1][j - 4];
        }
    }
    ll ans = 0;
    for(int j = 3 * n; j <= 4 * n;j ++) {
        ans += f[n][j];
    }
    ll sum = pow(4, n);
    cout << ans / gcd(ans, sum) << '/' << sum / gcd(ans, sum);
}