Submission #18525631


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((b1[:, :],i8,i8,i8,i8), cache=True)
@njit
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 = list(map(int, input().split()))
n = sum(vs)
main(vs,n)

Submission Info

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

Judge Result

Set Name All
Score / Max Score 0 / 6
Status
AC × 2
WA × 1
TLE × 1
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 TLE 2194 ms 120120 KB
01 WA 1275 ms 120816 KB
90 AC 1139 ms 119984 KB
91 AC 1137 ms 120348 KB