NC23413 小A买彩票

链接：https://ac.nowcoder.com/acm/problem/23413
来源：牛客网

题目描述

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

输入描述:

一行一个整数N，为小A购买的彩票数量一行一个整数N，为小A购买的彩票数量一行一个整数N，为小A购买的彩票数量

输出描述:

输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。输出一个最简分数a/b，表示小A不亏本的概率。
\\若概率为1，则输出1/1，概率为0，则输出0/1。输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。

思路：

$dp[i][j]$ 表示前 $i$ 张彩票可能获得 $j$ 元收获的种类数，每张彩票对应的可能价值为+1,+2,+3,+4。

转移方程：

当这张彩票价值为1元时： $dp[i][j]+=dp[i-1][j-1]$

当这张彩票价值为2元时： $dp[i][j]+=dp[i-1][j-2]$

当这张彩票价值为3元时： $dp[i][j]+=dp[i-1][j-3]$

当这张彩票价值为4元时： $dp[i][j]+=dp[i-1][j-4]$

且令 $dp[0][0]=1$ ，当不符合条件时比如： $dp[2][1],dp[3][2]$ 时 $dp[i][j]\equiv0$ 。

总共的可能数为: $sum=4^n$ ，不亏本的可能数为： $ans=\sum_{3*n}^{4*n}dp[n][j]$

不亏本的概率为： $\frac{ans}{sum}$ 约分后的值

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;
ll dp[35][130];
ll qp(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
int main(){
    int 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=qp(4,n);
    cout<<ans/__gcd(ans,sum)<<"/"<<sum/__gcd(ans,sum)<<endl;
}