結果

問題 No.3432 popcount & sum (Hard)
コンテスト
ユーザー startcpp
提出日時 2026-01-11 15:37:08
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,675 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 880 ms
コンパイル使用メモリ 112,668 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 15:37:27
合計ジャッジ時間 1,533 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <atcoder/modint>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;
using mint = modint998244353;

const int C = 60;
mint dpCnt[C + 1][2 * C + 1][2][2][2];	//(i, pop(a) - pop(b) + C, a=n, b=n, a=b)
mint dpSum[C + 1][2 * C + 1][2][2][2];

signed main() {
	int n, i, j, k, l, m, a, b;
	cin >> n;

	dpCnt[C][C][1][1][1] = 1;
	dpSum[C][C][1][1][1] = 0;

	for (i = C; i > 0; i--) {
		for (j = 0; j <= 2 * C; j++) {
			rep(k, 2) {
				rep(l, 2) {
					rep(m, 2) {
						if (dpCnt[i][j][k][l][m] == 0) continue;
						rep(a, 2) {
							rep(b, 2) {
								if (k == 1 && a > (n >> (i - 1)) % 2) continue;
								if (l == 1 && b > (n >> (i - 1)) % 2) continue;
								if (m == 1 && a > b) continue;
								
								int nj = j;
								if (a == 1 && b == 0) nj++;
								if (a == 0 && b == 1) nj--;
								int nk = k && (a == (n >> (i - 1)) % 2);
								int nl = l && (b == (n >> (i - 1)) % 2);
								int nm = m && (a == b);
								
								mint kiyo = ((a & b) << i);
								dpCnt[i - 1][nj][nk][nl][nm] += dpCnt[i][j][k][l][m];
								dpSum[i - 1][nj][nk][nl][nm] += dpSum[i][j][k][l][m] + dpCnt[i][j][k][l][m] * kiyo;
							}
						}
					}
				}
			}
		}
	}

	// dpSum[0][C][*][*][*]
	mint ans = 0;
	rep(k, 2) rep(l, 2) rep(m, 2) ans += dpSum[0][C][k][l][m];
	
	// なぜか2で割ると答えが合う
	ans *= mint(2).inv();

	cout << ans.val() << endl;
	return 0;
}
0