結果
問題 | 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);}