結果
問題 | No.1634 Sorting Integers (Multiple of K) Hard |
ユーザー | とりゐ |
提出日時 | 2021-07-07 12:28:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,537 ms / 3,000 ms |
コード長 | 1,112 bytes |
コンパイル時間 | 799 ms |
コンパイル使用メモリ | 86,760 KB |
実行使用メモリ | 114,220 KB |
最終ジャッジ日時 | 2023-10-14 01:53:19 |
合計ジャッジ時間 | 32,739 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 95 ms
71,428 KB |
testcase_01 | AC | 92 ms
71,544 KB |
testcase_02 | AC | 93 ms
71,524 KB |
testcase_03 | AC | 159 ms
78,672 KB |
testcase_04 | AC | 109 ms
77,592 KB |
testcase_05 | AC | 978 ms
89,800 KB |
testcase_06 | AC | 1,010 ms
89,128 KB |
testcase_07 | AC | 1,006 ms
89,744 KB |
testcase_08 | AC | 1,050 ms
99,544 KB |
testcase_09 | AC | 93 ms
71,452 KB |
testcase_10 | AC | 92 ms
71,632 KB |
testcase_11 | AC | 1,456 ms
111,752 KB |
testcase_12 | AC | 1,342 ms
106,176 KB |
testcase_13 | AC | 1,537 ms
112,524 KB |
testcase_14 | AC | 1,438 ms
110,464 KB |
testcase_15 | AC | 1,406 ms
110,920 KB |
testcase_16 | AC | 1,490 ms
112,452 KB |
testcase_17 | AC | 657 ms
88,356 KB |
testcase_18 | AC | 714 ms
88,904 KB |
testcase_19 | AC | 922 ms
94,604 KB |
testcase_20 | AC | 536 ms
87,352 KB |
testcase_21 | AC | 269 ms
80,008 KB |
testcase_22 | AC | 1,156 ms
95,072 KB |
testcase_23 | AC | 1,237 ms
100,396 KB |
testcase_24 | AC | 1,334 ms
105,656 KB |
testcase_25 | AC | 1,382 ms
109,424 KB |
testcase_26 | AC | 1,408 ms
109,108 KB |
testcase_27 | AC | 1,421 ms
109,980 KB |
testcase_28 | AC | 1,439 ms
111,200 KB |
testcase_29 | AC | 1,435 ms
112,336 KB |
testcase_30 | AC | 1,426 ms
110,888 KB |
testcase_31 | AC | 1,507 ms
114,220 KB |
ソースコード
import collections def bitDP(c,m): C=len(c) c=[int(i) for i in c] dp=[[] for i in range(1<<C)] dp[0].append(0) for i in range(1<<C): j=bin(i).count('1') for k in range(C): if (i>>k)&1==0: for l in dp[i]: dp[i+2**k].append((l+q[m+k]*c[j])%p) cnt=1 for i in collections.Counter(c).values(): cnt*=fact[i] t=collections.Counter(dp[-1]) for i in t: t[i]//=cnt return t import itertools n,p=map(int,input().split()) c=list(map(int,input().split())) a=[] for i in range(9): for j in range(c[i]): a.append(str(i+1)) all=tuple(itertools.combinations(a,n//2)) ans=0 q=[1]*(n+1) for i in range(1,n+1): q[i]=(q[i-1]*10)%p fact=[1]*(n+1) for i in range(1,n+1): fact[i]=fact[i-1]*i s=set() for x in all: y=''.join(x) if y not in s: s.add(y) else: continue b=a.copy() for i in x: b.remove(i) d1=bitDP(x,(n+1)//2) d2=bitDP(b,0) #print(d1,d2) #print(len(d1),len(d2)) #print(x,b) if 0 in d1 and 0 in d2: ans+=d1[0]*d2[0] for i in d1: if p-i in d2: ans+=d1[i]*d2[p-i] #print(x,b,d1[i]*d2[p-i]) print(ans)