Submission #18525646


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


import numpy as np
from numba import njit, b1, i4, i8, f8
@njit((i8[:],i8), cache=True)
def main(vs, n):
    M = 10**9+7 # 出力の制限
    N = 300 # 必要なテーブルサイズ
    g1 = [0] * (N+1) # 元テーブル
    g2 = [0] * (N+1) #逆元テーブル
    inverse = [0] * (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

    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)
vs = np.array(list(map(int, input().split())), dtype=np.int64)
n = sum(vs)
main(vs,n)

Submission Info

Submission Time
Task O - 文字列
User shotoyoo
Language Python (3.8.2)
Score 0
Code Size 1804 Byte
Status WA
Exec Time 1601 ms
Memory 106868 KB

Judge Result

Set Name All
Score / Max Score 0 / 6
Status
AC × 2
WA × 2
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 WA 1601 ms 106232 KB
01 WA 675 ms 106764 KB
90 AC 517 ms 106868 KB
91 AC 529 ms 105588 KB