結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const long long mod = 998244353;
vector<vector<long long>> c(64, vector<long long> (64));

long long com(int n, int r){
  if(n-r < 0 || r < 0)return 0;
  return c[n-r][r];
}

long long pop_count(long long x){
  long long r = 0;
  while(x){
    if(x&1)r++;
    x /= 2;
  }
  return r;
}

long long modpow(long long n, long long r){
  long long ans = 1;
  while(r){
    if(r%2)ans = ans * n % mod;
    n = n * n % mod;
    r /= 2;
  }
  return ans;
}

long long inverse(long long n){
  return modpow(n, mod-2);
}

vector<long long> pc_count_s(long long I){
  vector<long long> r(60);
  if(I == 0){
    r[0] = 1;
    return r;
  }
  int k = 0;
  while(I>1ll<<k)k++;
  for(int i = 0; i <= k; i++)r[i] = com(k, i);
  return r;
}

vector<long long> pc_count(long long n){
  vector<long long> r(60), s(60);
  if(n == 0){
    r[0] = 1;
    return r;
  }
  long long i = 1ll<<59;
  while(!(n&i))i/=2;
  if(i-1 != 1)r = pc_count_s(i-1);
  else r = pc_count(i-1);
  s = pc_count(n-i);
  rep(i, 59)r[i+1] = (r[i+1]+s[i])%mod;
  return r;
}

vector<long long> pc_count_i(long long n, long long i){
  vector<long long> r(60), s(60), t(60);
  int a;
  if(n<i)return r;
  if(n<i*2)return pc_count(n-i);
  s = pc_count(i-1);
  t = pc_count(n/(i*2)-1);
  rep(i, 60)rep(j, 60-i)r[i+j] = (r[i+j]+s[i]*t[j])%mod;
  s = pc_count_i(n%(i*2), i);
  a = pop_count(n/(i*2));
  rep(i, 60-a)r[i+a] = (r[i+a] + s[i])%mod;
  return r;
}

long long com2(long long n){
  return n%mod*((n-1)%mod)%mod*inverse(2)%mod;
}

int main(){
  c[0][0] = 1;
  rep(i, 64)rep(j, 64){
    if(i)c[i][j] += c[i-1][j];
    if(j)c[i][j] += c[i][j-1];
    c[i][j] %= mod;
  }
  long long n, ans = 0;
  vector<long long> v(60);
  cin >> n;
  ans = n%mod*((n+1)%mod)%mod*inverse(2)%mod;
  for(long long i = 1; i <= n; i *= 2){
    v = pc_count_i(n, i);
    for(long long x: v)ans = (ans + i%mod*com2(x)%mod)%mod;
  }
  cout << ans << endl;
}
0