小A买彩票（dp）

题意：

四种彩票中奖金额分别为1，2，3，4，且各种金额中奖率相等（良心）,小A买了n张彩票，问不亏本概率为多少？

分析：

模拟几次n发现，n每个中奖金额出现的概率总是由第n-1的概率转移过来的，具体转移方式有4种1，2，3，4，统计可行方式相加即可。因此我们可以用dp进行解决。

设dp[i][j]：前i张彩票中奖为j元的方案数。
转移方程：dp[i][j] += dp[i-1][j-k] 其中1≤k≤4 k≤j
初始dp[0][0]等于1

买n张彩票共有4^n方案数cnt
符合题意方案数为：sum（dp[n][j]）,3n<=j<=4n
最后答案为sum/cnt(gcd化简)

代码：

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
ll dp[35][150];
ll n,i,j,cnt;
int main()
{
    scanf("%lld",&n);
    dp[0][0]=1;
    for(i=1;i<=n;i++){
        for(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 sum=0;
    for(j=3*n;j<=4*n;j++){
        sum+=dp[n][j];//符合条件的方案数
    }
    cnt=(ll)pow(4,n);//总方案数
    while(__gcd(sum,cnt)!=1){
        ll t=__gcd(sum,cnt);
        sum=sum/t;
        cnt=cnt/t;
    }
    printf("%lld/%lld",sum,cnt);
}