Submission #18525551


Source Code Expand

Copy
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

### 素数の逆元とCombination

M = 10**9+7 # 出力の制限
N = 300 # 必要なテーブルサイズ
g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 
for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 
def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
def perm(n, r, M):
    if (r<0 or r>n):
        return 0
    return (g1[n] * g2[n-r]) % M

vs = list(map(int, input().split()))
n = sum(vs)
dp = [0]*(n+1)
dp[0] = 1
s = 0
for v in vs:
    if v==0:
        continue
    ndp = [0]*(n+1)
    for j in range(n+1):
        if dp[j]==0:
            continue
        for a in range(s+1-j+1):
            for b in range(j+1):
                ndp[j+v-a-b-b] += dp[j] * cmb(s+1-j,a,M) * cmb(j,b,M) * cmb(v-1,a+b-1,M)
                ndp[j+v-a-b-b] %= M
#                 print(a,b,dp[j] * cmb(s+1-j,a,M) * cmb(j,b,M) * cmb(v-1,a+b-1,M))
    s += v
    dp = ndp
#     print(dp)
ans = dp[0]
print(ans%M)

Submission Info

Submission Time
Task O - 文字列
User shotoyoo
Language PyPy3 (7.3.0)
Score 0
Code Size 1479 Byte
Status TLE
Exec Time 2207 ms
Memory 77780 KB

Judge Result

Set Name All
Score / Max Score 0 / 6
Status
AC × 3
TLE × 1
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 TLE 2207 ms 77780 KB
01 AC 670 ms 75444 KB
90 AC 57 ms 62380 KB
91 AC 57 ms 62512 KB