結果
問題 |
No.3030 Kruskal-Katona
|
ユーザー |
![]() |
提出日時 | 2025-02-02 19:01:55 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 3,424 ms |
コンパイル使用メモリ | 128,932 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-07 22:40:07 |
合計ジャッジ時間 | 4,575 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import std.algorithm, std.array, std.conv, std.stdio, std.typecons, std.range; ulong[] solve(ulong N, ulong i) { if (N == 0) return []; // special case if (i == 1) return [N]; ulong Ni = i; ulong b = 1; while (1) { auto b2 = binom(Ni+1, i); if (b2 > N) break; else ++Ni, b = b2; } return [Ni] ~ solve(N - b, i-1); } void main() { auto tmp = readln.split.to!(ulong[]); auto seq = solve(tmp[0], tmp[1]); auto ans = seq.map!(i => i.to!string ~ " ").reduce!`a ~ b`[0 .. $-1]; writeln(ans); } ulong binom(ulong N, ulong M) { // special case if (M == 0) return 1; if (M == 1) return N; if (M == 2) return N*(N-1)/2; if (M == 3) return N*(N-1)*(N-2)/6; auto powers = new ulong[primes.length]; auto numers = iota(N-M+1, N+1).map!(n => prime_decomposition(n)), denoms = iota(1, M+1).map!(n => prime_decomposition(n)); foreach (ns; numers) powers[] += ns[]; foreach (ds; denoms) powers[] -= ds[]; return multiply(powers); } // calculate primes immutable primes = list_primes(10^^4); ulong[] list_primes(ulong N) { auto is_not_prime = new bool[N+1]; is_not_prime[0] = is_not_prime[1] = true; foreach (n; 2 .. N+1) { ulong i = 2; while (n*i <= N) { is_not_prime[n * i] = true; ++i; } } return iota(N+1).filter!(p => !is_not_prime[p]).array; } ulong[] prime_decomposition(ulong N) { assert (N > 0); auto result = new ulong[primes.length]; foreach (i, p; primes) { while (N % p == 0) { N /= p; ++result[i]; } if (N == 1) break; } return result; } ulong multiply(ulong[] prime_powers) { auto result = 1U; foreach (i, n; prime_powers) { result *= primes[i]^^n; } return result; }