結果

問題 No.3431 popcount & sum (Easy)
コンテスト
ユーザー kwm_t
提出日時 2026-01-11 14:56:51
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,890 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,739 ms
コンパイル使用メモリ 385,552 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 14:56:59
合計ジャッジ時間 7,040 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
mint solve(long long n, int mask) {
	vector dp(61, vector(2, vector<mint>(61)));
	dp[60][0][0] = 1;
	rrep(i, 60) {
		// i+1->i
		int bit = 1 & (n >> i);
		{//0->0
			auto type00 = [&]()->void {
				if (i == mask && bit == 0)return;
				rep(k, 61) {
					if (dp[i + 1][0][k] == 0)continue;
					dp[i][0][k + bit] += dp[i + 1][0][k];
				}
			};
			type00();
		}
		{//0->1
			auto type01 = [&]()->void {
				if (bit == 0)return;
				if (i == mask)return;
				rep(k, 61) {
					if (dp[i + 1][0][k] == 0)continue;
					dp[i][1][k] += dp[i + 1][0][k];
				}
			};
			type01();
		}
		{//1->1
			auto type11 = [&]()->void {
				rep(j, 2) {
					if (mask == i && j == 0)continue;
					rep(k, 61) {
						if (dp[i + 1][1][k] == 0)continue;
						dp[i][1][k + j] += dp[i + 1][1][k];
					}
				}
			};
			type11();
		}
	}
	/*rep(i, 61)rep(j, 2)rep(k, 61) {
		if (dp[i][j][k] == 0)continue;
		cout << i << " " << j << " " << k << " " << dp[i][j][k].val() << endl;
	*/
	mint ret = 0;
	rep(k, 61) {
		mint cnt = dp[0][0][k] + dp[0][1][k];
		ret += ((mint)(1LL << mask)) *cnt * (cnt - 1) / 2;
	}
	return ret;
}
#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
inline int __builtin_ctz(unsigned int n) { unsigned long i; _BitScanForward(&i, n); return i; }
inline int __builtin_ctzll(unsigned long long n) { unsigned long i; _BitScanForward64(&i, n); return i; }
inline int __builtin_clz(unsigned int n) { unsigned long i; _BitScanReverse(&i, n); return i; }
inline int __builtin_clzll(unsigned long long n) { unsigned long i; _BitScanReverse64(&i, n); return i; }
#endif
void test(int n) {
	mint ret = 0;
	rep(i, n + 1)rep2(j, i + 1, n + 1) {
		if (__builtin_popcount(i) == __builtin_popcount(j))ret += i & j;
	}
	cout << ret.val() << endl;
	rep(i, n + 1)ret += i;
	cout << ret.val() << endl;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	long long n; cin >> n;
	//test(n);
	mint ans = 0;
	rep(i, 60) {
		ans += solve(n, i);
		//break;
	}
	ans += (mint(1 + n))*n / 2;
	cout << ans.val() << endl;
	return 0;
}
0