Submission #18525744


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 = np.zeros(N+1, dtype=np.int64) # 元テーブル
    g2 = np.zeros(N+1, dtype=np.int64) #逆元テーブル
    inverse = np.zeros(N+1, dtype=np.int64) #逆元テーブル計算用テーブル
    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 2045 Byte
Status WA
Exec Time 832 ms
Memory 106528 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 832 ms 105716 KB
01 WA 550 ms 105668 KB
90 AC 505 ms 106528 KB
91 AC 517 ms 106460 KB