之前算法周周练8写过,直接粘过来,复制完乱码......,贴的图片

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define mod 1e9+7
using namespace std;
ll dp[31][121]={0};//表示赚的数目

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    IOS
    dp[0][0]=1;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=4*n;j++)
        {
            if(j-1>=0)
                dp[i][j]+=dp[i-1][j-1];
            if(j-2>=0)
                dp[i][j]+=dp[i-1][j-2];
            if(j-3>=0)
                dp[i][j]+=dp[i-1][j-3];
            if(j-4>=0)
                dp[i][j]+=dp[i-1][j-4];
        }
    }
    ll a=0;
    for(int i=n*3;i<=121;i++)
        a+=dp[n][i];
    ll b=pow(4,n);
    ll c=a/gcd(a,b);
    ll d=b/gcd(a,b);
    printf("%lld/%lld\n",c,d);
    return 0;
}