結果
問題 | No.3030 Kruskal-Katona |
ユーザー |
![]() |
提出日時 | 2025-02-21 22:23:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 563 ms / 2,000 ms |
コード長 | 1,137 bytes |
コンパイル時間 | 476 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 241,416 KB |
最終ジャッジ日時 | 2025-02-21 22:24:29 |
合計ジャッジ時間 | 17,508 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
def cmb(n, r, p): if (r < 0) or (n < r): return 0 r = min(r, n - r) return fact[n] * factinv[r] * factinv[n-r] % p p=100000000000000003 N = 10**6 # N は必要分だけ用意する fact = [1, 1] # fact[n] = (n! mod p) factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p) inv = [0, 1] # factinv 計算用S for i in range(2, N + 1): fact.append((fact[-1] * i) % p) inv.append((-inv[p % i] * (p // i)) % p) factinv.append((factinv[-1] * inv[-1]) % p) def solve(N,i): if i==1: return [N] l=N ans=[] last=10**6 for i in range(i,0,-1): left,right=1,last while right-left>1: mid=(left+right)//2 if cmb(mid,i,p)<=N: left=mid else: right=mid ans.append(left) N-=cmb(left,i,p) last = left if N==0: break assert N==0 assert min(ans)>=1 assert len(ans)==len(set(ans)) return ans N,i=map(int,input().split()) print(*solve(N,i)) exit() N=10**8 import random for i in range(1000): n=97 i=random.randint(1,10) print(n,i,solve(n,i))