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
Exec Time 2109 ms
Memory 80984 KB

Judge Result

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 2108 ms 69336 KB
12.txt 2108 ms 69848 KB
13.txt 2108 ms 69336 KB
14.txt 2107 ms 69156 KB
15.txt 2108 ms 68696 KB
16.txt 2109 ms 80472 KB
17.txt 2109 ms 79704 KB
18.txt 2109 ms 80984 KB
19.txt 2108 ms 80344 KB
20.txt 2109 ms 80088 KB
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