Submission #18525894


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):
                ind = j+v-a-b-b
                ndp[ind] += ((dp[j] * cmb(s+1-j,a,M) % M) * cmb(j,b,M) % M) * cmb(v-1,a+b-1,M)
                ndp[ind] %= 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 1516 Byte
Status TLE
Exec Time 2208 ms
Memory 77464 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 2208 ms 77464 KB
01 AC 739 ms 74572 KB
90 AC 60 ms 62280 KB
91 AC 57 ms 62148 KB