小A买彩票（dp）

题意：略

题记：
dp[i][j]表示前i张彩票能组成总金额为j元的方案数
第i张彩票有1,2,3,4元四种选择，所以总金额为j的情况可以由四种情况转移过来。
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4];

总方案数是4的n次方种，所有方案数中总金额大于等于3*n的就是不亏本的，将数量记录下来，最后将两个数约分之后输出即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=200;
ll dp[N][N];
//dp[i][j]表示前i张彩票能组成总金额为j元的方案数

ll qpow(ll a,ll b){//快速幂
    ll sum=1;
    while(b){
        if(b&1)sum=sum*a;
        b>>=1;
        a=a*a;
    }
    return sum;
}

ll gcd(ll a,ll b){
    while(b){
        ll t=a%b;
        a=b;
        b=t;
    }
    return a;
}

int main(){
    ll n;
    cin>>n;
    //dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=i*4;j++)
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4];
    ll ans=0;
    ll sum=qpow(4,n);//总方案数
    for(int i=3*n;i<=4*n;i++)
        ans+=dp[n][i];
    ll g=gcd(ans,sum);//求出最大公因子
    cout<<ans/g<<'/'<<sum/g<<endl;
    return 0;
}