結果
問題 |
No.1631 Sorting Integers (Multiple of K) Easy
|
ユーザー |
|
提出日時 | 2021-07-30 21:52:45 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,400 bytes |
コンパイル時間 | 134 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 16,256 KB |
最終ジャッジ日時 | 2024-09-15 23:53:40 |
合計ジャッジ時間 | 5,296 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 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 f=1 from math import factorial for v in C: f*=factorial(v) print(dp[-1][0]//f)