C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 472K, 提交时间: 2023-07-10 17:50:48

#include<bits/stdc++.h>
using namespace std;
long long n,dp[32][125],sum,a,b;
int main()
{
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=4*n;j++)
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4];
    for(int j=3*n;j<=4*n;j++)
        sum+=dp[n][j];
    b=pow(4,n);
    a=gcd(sum,b);
    cout<<sum/a<<"/"<<b/a;
    return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 43ms, 内存消耗: 19564K, 提交时间: 2020-07-20 20:54:09

import sys, os

def gcd(a, b):
	while b: a, b = b, a % b;
	return a

n = int(input())

dp = [1] + [0] * (4 * n)

for _ in range(n):
	t, dp = dp, [0] * (4 * n + 1)
	for i in range(len(dp) - 1, 0, -1):
		for j in range(1, 5):
			if i - j >= 0: dp[i] += t[i - j]

a, b = 0, sum(dp)
for i in range(3 * n, len(dp)): a += dp[i]

g = gcd(a, b)
print("{}/{}".format(a // g, b // g))

Python3(3.5.2) 解法, 执行用时: 157ms, 内存消耗: 5072K, 提交时间: 2020-05-26 20:05:37

import fractions
from functools import lru_cache
n = int(input())
@lru_cache(maxsize = 30 * 4 * 30)
def dp(cur, u):
    if u == 0: return cur >= n*3
    ans = fractions.Fraction(0, 1)
    for i in [1, 2, 3, 4]: ans += fractions.Fraction(1, 4) * dp(cur + i, u - 1)
    return ans
ret = dp(0, n)
if ret == 1: print('1/1')
elif ret == 0: print('0/1')
else: print(ret)

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 460K, 提交时间: 2023-06-12 11:14:10

#include<bits/stdc++.h>
using namespace std;
long long dp[40][130];
int main()
{
	int n;
	cin>>n;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;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];
	long long a=0,b=pow(4,n),c;
	for(int i=3*n;i<=4*n;i++)  a+=dp[n][i];
	c=__gcd(a,b);
	printf("%lld/%lld",a/c,b/c);
}