Submission #18525914


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
def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    return CMB[n][r]
CMB = [[0]*300 for _ in range(300)]
for i in range(300):
    for j in range(300):
        CMB[i][j] = _cmb(i,j,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 1720 Byte
Status AC
Exec Time 496 ms
Memory 75184 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 496 ms 74988 KB
01 AC 127 ms 75184 KB
90 AC 70 ms 71020 KB
91 AC 68 ms 71456 KB