結果
問題 | No.737 PopCount |
ユーザー |
![]() |
提出日時 | 2018-05-02 22:31:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 1,862 ms |
コンパイル使用メモリ | 192,500 KB |
最終ジャッジ日時 | 2025-01-05 10:28:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include<bits/stdc++.h>using namespace std;using int64 = long long;const int mod = 1e9 + 7;int64 N;int dp[64][2][64];int dp2[64][2][64];int ways(int idx, bool less, int popcount) {if(idx == -1) return popcount;if(~dp2[idx][less][popcount]) return dp2[idx][less][popcount];int ret = ways(idx - 1, less | ((N >> idx) & 1), popcount);if(less || ((N >> idx) & 1)) ret += ways(idx - 1, less, popcount + 1);return dp2[idx][less][popcount] = ret % mod;}int rec(int idx, bool less, int popcount) {if(idx == -1) return 0;if(~dp[idx][less][popcount]) return dp[idx][less][popcount];int64 ret = rec(idx - 1, less | ((N >> idx) & 1), popcount);if(less || ((N >> idx) & 1)) {ret += rec(idx - 1, less, popcount + 1);ret += 1LL * ways(idx - 1, less, popcount + 1) * ((1LL << idx) % mod) % mod;}return dp[idx][less][popcount] = ret % mod;}int main() {cin >> N;memset(dp, -1, sizeof(dp));memset(dp2, -1, sizeof(dp2));cout << rec(62, false, 0) << endl;}