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; }