Submission #18525809


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])%M * 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)
    return g1,g2,dp,inverse
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 6
Code Size 2078 Byte
Status AC
Exec Time 915 ms
Memory 106644 KB

Judge Result

Set Name All
Score / Max Score 6 / 6
Status
AC × 4
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 AC 915 ms 106164 KB
01 AC 547 ms 105484 KB
90 AC 499 ms 105968 KB
91 AC 516 ms 106644 KB