結果
問題 |
No.2711 Connecting Lights
|
ユーザー |
![]() |
提出日時 | 2024-03-31 14:20:24 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 79 ms / 5,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 1,923 ms |
コンパイル使用メモリ | 205,524 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 19:22:55 |
合計ジャッジ時間 | 3,259 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import std, core.bitop; bool chmin(T)(ref T SE, T MI) { if (SE > MI) { SE = MI; return true; } else { return false; } } bool chmax(T)(ref T SE, T MI) { if (SE < MI) { SE = MI; return true; } else { return false; } } int lowerBound(T)(T[] SE, T MI) { int lo = -1, hi = cast(int)(SE.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (SE[mid] < MI ? lo : hi) = mid; } return hi; } int upperBound(T)(T[] SE, T MI) { int lo = -1, hi = cast(int)(SE.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (SE[mid] > MI ? hi : lo) = mid; } return hi; } enum MO = 998244353; void main() { int N, M, K; readf("%s %s %s\n", N, M, K); if (M == 1) { writeln(1 << N); return; } auto dp = new long[][](2, 1 << N); int cur; dp[cur][(1 << N) - 1] = 1; foreach (i; 0 .. M) { int nxt = !cur; foreach (j; 0 .. 1 << N) { dp[nxt][j] = 0; } foreach (j; 0 .. 1 << N) { foreach (k; 0 .. 1 << N) { if (popcnt(j & k) >= K) { (dp[nxt][k] += dp[cur][j]) %= MO; } } } cur = nxt; } long ans; foreach (i; 0 .. 1 << N) { ans += dp[cur][i]; } ans %= MO; ans.writeln; }