Submission #18525883


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] % M) * 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 6
Code Size 1520 Byte
Status AC
Exec Time 863 ms
Memory 69772 KB

Judge Result

Set Name All
Score / Max Score 6 / 6
Status
AC × 4
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 AC 863 ms 69772 KB
01 AC 206 ms 68860 KB
90 AC 56 ms 61896 KB
91 AC 57 ms 61900 KB