Submission #18525691


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
                    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 1951 Byte
Status WA
Exec Time 1695 ms
Memory 106804 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 1695 ms 106804 KB
01 WA 663 ms 105528 KB
90 AC 544 ms 106732 KB
91 AC 527 ms 106348 KB