Submission #2997741


Source Code Expand

Copy
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#mod table !
mod=998244353
table=[1]*1002
s=1
for i in range(1,1002):
    s*=i
    table[i]=s%mod
rtable=[1]*1002
s=1
for i in range(1,1002):
    s*=pow(i,mod-2,mod)
    rtable[i]=s%mod
#jk
dp=[[0]*(N+1) for i in range(N+2)]
dp[N+1][0]=1
for i in range(N,0,-1):
    for j in range(N+1):
        num=dd[i]+j
        if num>N:
            continue
        k=0
        while k*i<=num:
            #print(i,j,k*i)
            num=dd[i]+j
            C=table[num]
            C*=rtable[num-k*i]
            C%=mod
            C*=pow(rtable[i],k,mod)
            C%=mod
            C*=rtable[k]
            C%mod
            dp[i][num-k*i]+=C*dp[i+1][j]
            dp[i][num-k*i]%=mod
            k+=1
print(dp[1][0])

Submission Info

Submission Time
Task F - チーム分け
User okumura
Language PyPy3 (2.4.0)
Score 0
Code Size 884 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 180 ms 38256 KB
02.txt 178 ms 38256 KB
03.txt 175 ms 38256 KB
04.txt 176 ms 38384 KB
05.txt 179 ms 38256 KB
06.txt 332 ms 48472 KB
07.txt 308 ms 46936 KB
08.txt 308 ms 46936 KB
09.txt 312 ms 47064 KB
10.txt 321 ms 47064 KB
11.txt
12.txt
13.txt
14.txt
15.txt
16.txt
17.txt
18.txt
19.txt
20.txt
21.txt 178 ms 38256 KB
22.txt 178 ms 38256 KB
23.txt 176 ms 38256 KB
24.txt 179 ms 38256 KB
s1.txt 175 ms 38384 KB
s2.txt 177 ms 38256 KB
s3.txt 180 ms 38256 KB