小A买彩票（简单计数）

题目：

小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。
输出一个最简分数a/b，表示小A不亏本的概率。
若概率为1，则输出1/1，概率为0，则输出0/1。
0≤n≤30

做法：

n这么小。直接枚举所有情况。
定义状态(i,j,k,l)表示金额分别为1、2、3、4元的彩票分别有i、j、k、l张。
直接3重循环枚举状态。然后看一下亏不亏本。不亏则加上这种状态的出现次数：。然后所有情况数。答案就是约过的。

代码：

#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 50;
ll c[N][N];
void init(int n){
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i){
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j){
            c[i][j] = c[i-1][j]+c[i-1][j-1];
        }
    }
}
int main(void){
    IOS;
    int n; cin >> n;
    init(n);
    ll fz = 0, fm = 1;
    for (int i = 1; i <= n; ++i) fm *= 4;
    for (int i = 0; i <= n; ++i){
        for (int j = 0; i+j <= n; ++j){
            for (int k = 0; i+j+k <= n; ++k){
                int l = n-i-j-k;
                if (3*n <= 1*i+2*j+3*k+4*l){
                    fz += c[n][i]*c[n-i][j]*c[n-i-j][k];
                }
            }
        }
    }
    ll g = __gcd(fz, fm);
    fz /= g, fm /= g;
    cout << fz << '/' << fm << endl;
    return 0;
}