Submission #18525716


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 = np.zeros(n+1, dtype=np.int64)
    dp[0] = 1
    s = 0
    for v in vs:
        if v==0:
            continue
        ndp = np.zeros(n+1, dtype=np.int64)
        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
                    val = dp[j] * cmb(s+1-j,a,M) % M
                    val *= cmb(j,b,M)
                    val %= M
                    val *= cmb(v-1,a+b-1,M)
                    val %= M
                    ndp[ind] += val
                    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 1991 Byte
Status WA
Exec Time 1584 ms
Memory 106308 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 1584 ms 106292 KB
01 WA 668 ms 106292 KB
90 AC 510 ms 106308 KB
91 AC 523 ms 105616 KB