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