結果
問題 | No.737 PopCount |
ユーザー |
![]() |
提出日時 | 2018-09-28 21:50:14 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,862 bytes |
コンパイル時間 | 624 ms |
コンパイル使用メモリ | 76,788 KB |
最終ジャッジ日時 | 2025-01-30 11:47:15 |
合計ジャッジ時間 | 1,150 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In instantiation of ‘struct comb_util<long long int, 1000000007, 30000>’: main.cpp:59:6: required from here main.cpp:16:32: error: ‘comb_util<Int, MOD, N>::fc’ has incomplete type 16 | std::array<Int, N + 1> fc, ifc; | ^~ In file included from /usr/include/c++/13/bits/stl_map.h:63, from /usr/include/c++/13/map:63, from main.cpp:3: /usr/include/c++/13/tuple:2019:45: note: declaration of ‘struct std::array<long long int, 30001>’ 2019 | template<typename _Tp, size_t _Nm> struct array; | ^~~~~ main.cpp:16:36: error: ‘comb_util<Int, MOD, N>::ifc’ has incomplete type 16 | std::array<Int, N + 1> fc, ifc; | ^~~ /usr/include/c++/13/tuple:2019:45: note: declaration of ‘struct std::array<long long int, 30001>’ 2019 | template<typename _Tp, size_t _Nm> struct array; | ^~~~~
ソースコード
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <string> #include <iomanip> #include <algorithm> #include <cmath> #include <stdio.h> using namespace std; #define int long long int MOD = 1000000007; template <typename Int, Int MOD, int N> struct comb_util { std::array<Int, N + 1> fc, ifc; comb_util() { fc[0] = 1; for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD; ifc[N] = inv(fc[N]); for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD; } Int fact(Int n) { return fc[n]; } Int inv_fact(Int n) { return ifc[n]; } Int inv(Int n) { return pow(n, MOD - 2); } Int pow(Int n, Int a) { Int res = 1, exp = n; for (; a; a /= 2) { if (a & 1) res = res * exp % MOD; exp = exp * exp % MOD; } return res; } Int perm(Int n, Int r) { if (r < 0 || n < r) return 0; else return fc[n] * ifc[n - r] % MOD; } Int binom(Int n, Int r) { if (n < 0 || r < 0 || n < r) return 0; return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD; } Int homo(Int n, Int r) { if (n < 0 || r < 0) return 0; return r == 0 ? 1 : binom(n + r - 1, r); } }; using comb = comb_util<long long, 1000000007, 30000>; comb cb; int pc(int N) { int res = 0; while (N > 0) { res += N % 2; N /= 2; } return res; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; int a = 1; int n = N; int res = 0; for (int i = 0; i < 61; i++) { if ((N & a) != 0) { n ^= a; int p = pc(n); for (int j = 0; j <= i; j++) { int k; if (j == 0) { k = 0; } else { k = (((a - 1) % MOD) * cb.binom(i - 1, j - 1)) % MOD; } res = (res + (((j + p) * k) % MOD)) % MOD; res = (res + (((n % MOD)*(j + p) % MOD)*cb.binom(i, j) % MOD)) % MOD; } } a *= 2; } res = (res + (((N%MOD)*pc(N)) % MOD)) % MOD; cout << res << endl; }