小A买彩票

image-20240430004133242

cf没做出来，跑过来写道牛客

1
2
3
4
5
6
dp[i][j]表示前i张彩票中奖j元的方案数
那么易得转移方程
dp[i][j] += dp[i-1][j-k] 其中1≤k≤4 k≤j
边界为dp[0][0]
买n张彩票，每张彩票有四种情况，总的方案数就是sum=4^n
计算出来ans=sum(dp[n][k]) 其中k>=3n

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
ll dp[35][150];///对于前i张中奖j元的方案数
int main(){
    ll n;cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;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];
        }
    }
    ll ans=0;
    for(int i=3*n;i<=4*n;i++) ans += dp[n][i];
    ll sum=((ll)1<<(n<<1));
    cout<<ans/__gcd(ans,sum)<<"/"<<sum/__gcd(ans,sum)<<endl;
    return 0;
}