小A买彩票

dp题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=37;
ll n,ans,sum;  //记得开ll
ll f[N][4*N];  //f[i][j]表示前i张彩票获得j元的方案数  //这里的方案数和位置有关即类似A3取2(=2)这种，而非C3取2(=1)
ll ksm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
int main() {
    cin >> n;
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=i;j<=4*i;++j){
            for(int k=1;k<=4&&k<=j;++k)
                f[i][j]+=f[i-1][j-k];
        }
    }
    for(int j=3*n;j<=4*n;++j) ans+=f[n][j];
    //sum=ksm(4,n);
    sum=(ll) 1 << (n<<1);
    ll z=__gcd(ans,sum);
    cout << ans/z << "/" << sum/z;
    return 0;
}