【每日一题】小A买彩票

题目

已知购买一张彩票需要 3 元，而彩票中奖的金额分别为 1、2、3、4 元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。
现在小A连续购买了 n 张彩票，求至少能够不亏本的概率是多少。

解题思路

动态规划：

$dp[i][j]$ 表示购买了 $i$ 张彩票并得到 $j$ 元金额的方法数目。
状态转移方程为： $dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + dp[i-1][j-4]$ 。
不亏本的数目总数为 $cnt = \sum_{j=3n}^{4n}dp[n][j]$ 。
所有方法的总数为 $total = 4^n$ 。
返回 $cnt / total$ 。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    long long n;
    cin >> n;
    vector<vector<long long>> dp(n+1, vector<long long>(4*n+1,0));
    dp[0][0] = 1;
    for(int i=1; i<=n; ++i){
        for(int j=i; j<=4*i; ++j){
            if(j>=1)
                dp[i][j] += dp[i-1][j-1];
            if(j>=2)
                dp[i][j] += dp[i-1][j-2];
            if(j>=3)
                dp[i][j] += dp[i-1][j-3];
            if(j>=4)
                dp[i][j] += dp[i-1][j-4];
        }
    }
    long long cnt = 0;
    for(int j=3*n; j<=4*n; ++j)
        cnt += dp[n][j];
    long long total = pow(4LL,n);
    long long k = __gcd(cnt, total);
    long long a = cnt / k;
    long long b = total / k;
    cout << a << "/" << b << endl;
    return 0;
}