题目链接：点此跳转
题目大意：
小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。
输入描述:
一行一个整数N，为小A购买的彩票数量一行一个整数N，为小A购买的彩票数量
输出描述:
输出一个最简分数a/b，表示小A不亏本的概率。 若概率为1，则输出1/1，概率为0，则输出0/1。输出一个最简分数a/b，表示小A不亏本的概率。 若概率为1，则输出1/1，概率为0，则输出0/1。
解题思路：
因为要求最简分数所以最后答案(ans,sum)要求一个gcd ，然后同除即可，还有因为n<=30，pow(4,30)超出了int范围，所以要开到longlong
dp[i][j] 代表买了i个彩票中了j块钱的个数 ， 最后的j要>=3*n才算不亏本（一张彩票3块钱）
Code：
#include<iostream> #include<cstring> using namespace std; typedef long long ll; ll dp[100][100]; ll qsm(ll a,ll b){ ll res=1; while(b){ if(b&1) res=res*a; b>>=1; a=a*a; } return res; } ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } int main(){ int n; scanf("%d",&n); if(n==0){ printf("1/1\n"); }else{ dp[0][0]=1; ll sum=qsm(4,n); for(int i=1;i<=n;i++){ for(int j=i;j<=4*i;j++){ for(int k=1;k<=4;k++){ if(j>=k) dp[i][j]+=dp[i-1][j-k]; } } } ll ans=0; for(int i=3*n;i<=4*n;i++) ans+=dp[n][i]; //>=3*n才算不亏本 ll g=gcd(ans,sum); printf("%lld/%lld\n",ans/g,sum/g); } return 0; }