Submission #2998265


Source Code Expand

Copy
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
dd=[0]*(N+2)

for a in A:
    dd[a]+=1
#mod table !
mod=998244353
table=[1]*(N+2)
s=1
for i in range(1,(N+2)):
    s*=i
    table[i]=s%mod
rtable=[1]*(N+2)
inv=[1]*(N+2)
s=1
for i in range(1,(N+2)):
    t=pow(i,mod-2,mod)
    inv[i]=t
    s*=t
    rtable[i]=s%mod
dp={0:1}
num=0
i=max(A)
while i>1:
    t=dd[i]
    ndp=defaultdict(int)
    for r,com in dp.items():
        new=t+r
        ndp[new]+=com
        #dp[i][num]+=dp[i+1][j]
        k=1
        C=1
        while k*i<=new:
            #print(i,j,k*i)
            C*=table[new-(k-1)*i]*rtable[i]*rtable[new-k*i]
            C%=mod
            C*=inv[k]
            ndp[new-k*i]+=(C*com)%mod
            ndp[new-k*i]%=mod
            k+=1
    dp=ndp
    i-=1
    #print(dp)
print(sum(dp.values())%mod)



Submission Info

Submission Time
Task F - チーム分け
User okumura
Language PyPy3 (2.4.0)
Score 600
Code Size 899 Byte
Status
Exec Time 1252 ms
Memory 77532 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 600 / 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 163 ms 38256 KB
02.txt 167 ms 38256 KB
03.txt 162 ms 38256 KB
04.txt 163 ms 38256 KB
05.txt 166 ms 38256 KB
06.txt 234 ms 44656 KB
07.txt 236 ms 45420 KB
08.txt 218 ms 43632 KB
09.txt 220 ms 43632 KB
10.txt 226 ms 44400 KB
11.txt 1074 ms 69980 KB
12.txt 1054 ms 68700 KB
13.txt 1002 ms 66396 KB
14.txt 1065 ms 69980 KB
15.txt 961 ms 67292 KB
16.txt 1252 ms 77532 KB
17.txt 1239 ms 76764 KB
18.txt 1225 ms 77020 KB
19.txt 1241 ms 76764 KB
20.txt 1214 ms 76892 KB
21.txt 168 ms 38256 KB
22.txt 169 ms 38256 KB
23.txt 163 ms 38256 KB
24.txt 163 ms 38256 KB
s1.txt 164 ms 38256 KB
s2.txt 162 ms 38256 KB
s3.txt 162 ms 38256 KB