結果
問題 |
No.1631 Sorting Integers (Multiple of K) Easy
|
ユーザー |
|
提出日時 | 2021-07-30 21:50:34 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,334 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 122,112 KB |
最終ジャッジ日時 | 2024-09-15 23:47:45 |
合計ジャッジ時間 | 5,822 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 5 WA * 5 TLE * 1 -- * 17 |
ソースコード
#!/usr/bin/python3.8 N,K=map(int,input().split()) C=list(map(int,input().split())) nums=[] from collections import defaultdict for i in range(1,10): nums+=[i]*C[i-1] dp=[defaultdict(int) for i in range(2**N)] dp[0][0]+=1 #########bit library ######### def popcount(a): return bin(a).count('1') #Sの部分集合の列挙、降順 def subset(S): T=S while T: T=S&(T-1) yield T #N桁の二進数のうち丁度Kbitだけ立っている数の列挙 #昇順 def Kbits(N,K): if N<K:raise ValueError if K==0:return [0] v=(1<<K)-1;MAX=1<<N while v<MAX: yield v x = v & (-v) y = v + x v = (v & ~y) // x >> 1 | y #S&v = v を満たすvの列挙、昇順 def flags(S): while S: v=S&(-S) S^=v yield v def flag_inds(S): while S: v=S&(-S) S^=v yield v.bit_length()-1 #1つだけビットが立っていないものの列挙、降順 def childs(S): tmp=S while tmp: v=tmp&(-tmp) tmp^=v yield S^v,v.bit_length()-1 def post(S): assert S>0 v=S&(-S) return S^v,v.bit_length()-1 #########bit library end######### for S in range(1,2**N): for P,j in childs(S): num=nums[j] for k,v in dp[P].items(): dp[S][(10*k+num)%K]+=v print(dp[-1][0])