結果

問題 No.3432 popcount & sum (Hard)
コンテスト
ユーザー MM
提出日時 2026-01-11 16:25:58
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 1,636 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,856 ms
コンパイル使用メモリ 283,680 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-11 16:26:11
合計ジャッジ時間 7,726 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
#define chmin(x,y) (x) = min((x),(y))
#define chmax(x,y) (x) = max((x),(y))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec vector
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back 
#define eb emplace_back

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
const ll mod = 998244353;
using mint = modint998244353;
const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};
// using Graph = vector<vector<pair<int,ll>>>;
using Graph = vector<vector<int>>;

int main(){
  // input
  ll n;
  cin >> n;

  // prep
  const int M = 60;
  vec binom(2*M,vec<mint>(2*M,0));
  binom[0][0] = 1;
  rep(i,2*M-1){
    binom[i+1][0] = 1;
    binom[i+1][i+1] = 1;
    rep(j,i)
      binom[i+1][j+1] = binom[i][j] + binom[i][j+1];
  }
  // ref: https://atcoder.jp/contests/abc406/submissions/65914933

  vec<int> bits(M);
  rep(i,M) bits[i] = (n & (1LL<<i)) ? 1 : 0;
  reverse(all(bits));
  
  // tmp[dig][pop][tight], res -> cnt[x][y]
  vec tmp(M+1,vec(M+1,vec<mint>(2,0)));
  vec cnt(M+1,vec<mint>(M+1,0));

  tmp[0][0][1] = 1;
  rep(i,M) rep(j,M+1) rep(k,2) rep(l,2){
    if(k && l && !bits[i]) continue;

    int nxt_k = (k && (l == bits[i]));
    tmp[i+1][j+l][nxt_k] += tmp[i][j][k];
    
    if(l && !k){
      for(int y = j; y < M; y++){
        cnt[M-1-i][y] += tmp[i][j][k] * binom[M-i-1][y-j];
      }
    }
  }

  // solve
  mint ans = (mint)n * (n+1) / (mint)2;

  rep(x,M+1){
    rep(y,M)
      ans += (mint)(1LL<<x) * cnt[x][y] * (cnt[x][y]-1) / 2;
  }
  
  // output
  cout << ans.val() << endl;
}
0