[每日一题] [NC23413] 小A买彩票

https://ac.nowcoder.com/acm/problem/23413

题目大意：N次独立的赌博，每次要花3元，等可能赚1，2，3，4，问保本概率。

比较简单的技术DP，只需要知道每种总和的选法即可。状态转移也比较直接。

//Pr[X1+...Xn>=3*n]
#include <iostream>
#include <vector>

using namespace std;

long long gcd(long long x, long long y) {
    if (x > y) return gcd(y, x);
    if (x == 0) return y;
    return gcd(y % x, x);
}

void doit(int N) {
    vector<long long> counts(N * 4 + 4, 0);
    counts[0] = 1;
    for (int i = 0; i < N; ++i) {
        vector<long long> new_counts(N * 4 + 4, 0);
        for (int j = 0; j < N * 4 + 4; ++j) {
            for (int curr = 1; curr <= 4; ++curr) {
                if (j >= curr) {
                    new_counts[j] += counts[j - curr];
                }
            }
        }
        counts = new_counts;
    }
    long long tot = 0;
    long long hit = 0;
    for (int i = 0; i < N * 4 + 4; ++i) {
        if (i >= N * 3) {
            hit += counts[i];
        }
        tot += counts[i];
    }
    long long g = gcd(tot, hit);
    printf("%lld/%lld\n", hit / g, tot / g);
}

int main() {
    int N;
    scanf("%d", &N);
    doit(N);
    return 0;
}