【每日一题】小A买彩票

题目描述
小A要买彩票，一张彩票3元，而彩票的中奖金额是1,2,3,4元，而且各种金额的中奖概率是一样的，现在他连续购买来n张彩票，他希望他至少能够不亏本的概率是多少?

输入描述
一行一个n,代表他购买的彩票数量

输出描述
输出一个－最简分数a/b，代表他不亏本的概率，

若概率为1，则输出1/1，概率为0,则输出0/1
0=<n<=30;
思路
对于n张彩票，开奖结果有4^n中，由于数据范围不是很大,那么我首先想到的是暴力，
我可以使用dp来做，设f[i][j]代表买来i张彩票获利为j的方案数，
彩票有中1元，2元，3元，4元四种情况，则有

最后把不亏本的方案数加起来除以4^n即可
附代码

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll dp[40][200]={1};

int main(){
   ll n,p,sum;
   dp[0][0]=1;
   cin>>n;
   p=1;
   for(int i=0;i<n;i++){
       p*=4;
   }
   for(int i=1;i<=n;i++){
       for(int j=1;j<=4*i;j++){
           for(int k=1;k<=4;k++){
               if(j-k>=0){
                   dp[i][j]+=dp[i-1][j-k];
               }
           }
       }
   }
   sum=0;
   for(int i=3*n;i<=4*n;i++){
       sum+=dp[n][i];
   }
   int q=__gcd(sum,p);
   cout<<sum/q<<"/"<<p/q<<endl;
   return 0;

}