結果
問題 |
No.737 PopCount
|
ユーザー |
![]() |
提出日時 | 2022-03-31 01:28:18 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,899 bytes |
コンパイル時間 | 668 ms |
コンパイル使用メモリ | 101,368 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 14:44:31 |
合計ジャッジ時間 | 1,380 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
import std.stdio, std.string, std.conv; import std.algorithm, std.math; import std.range; import std.container.rbtree, std.container.dlist; import std.container.binaryheap, std.container.array; import std.typecons; alias mstring = char[]; const long INF = 1L << 60L; const long mod = 1_000_000_000 + 7; void chmin (T)(ref T x, T y) { x = min(x, y); } void chmax (T)(ref T x, T y) { x = max(x, y); } // 単一の数値を取得 // readln.chomp.to!int; // or // int a; // readf("%s\n", a); // 複数の数値を取得(可変数個の場合推奨) // readln.chomp.split.map!(to!long).array // 複数の数値を取得(固定数個の場合、推奨) // int a, b; // readf("%s %s\n", &a, &b); // インデントを一個ずらして複数の数値を取得(累積和とかで1-indexedの方が良い時がある) // long[] vs = readln.chomp.split.map!(to!long).array; // vs = [0L] ~ vs; // 小数点は以下で指定 // double ret = 10.0; // writefln("%.12f", ret); // 配列の最後の要素は arr[$-1] でアクセスできる void main () { long N = readln.chomp.to!long; const int maxK = 62L; auto dp1 = new long[][][](maxK + 1, 2, maxK + 1); auto dp2 = new long[][][](maxK + 1, 2, maxK + 1); dp1[maxK][0][0] = 1L; for (long i = maxK; i > 0; i--) { long ni = (N >> (i - 1L)) & 1L; foreach (k; 0 .. 2) foreach (j; 0 .. maxK) foreach (d; 0L .. 2L) { if (k == 0 && d > ni) continue; int nk = cast(int)(k == 1 || d < ni); int nj = j + cast(int)(d == 1L); dp1[i - 1][nk][nj] += dp1[i][k][j]; dp1[i - 1][nk][nj] %= mod; dp2[i - 1][nk][nj] += (dp2[i][k][j] << 1L) + d * dp1[i][k][j]; dp2[i - 1][nk][nj] %= mod; } } long ret = 0L; foreach (j; 0 .. maxK + 1) { ret += ((dp2[0][0][j] + dp2[0][1][j]) % mod) * j; ret %= mod; } writeln(ret); }