Submission #18525578


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) * cmb(j,b,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 PyPy2 (7.3.0)
Score 0
Code Size 1500 Byte
Status TLE
Exec Time 2207 ms
Memory 82372 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 82372 KB
01 AC 667 ms 77960 KB
90 AC 51 ms 64652 KB
91 AC 48 ms 64892 KB