結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;

void solve(){
  using ll=long long;
  using mint=atcoder::modint998244353;
  ll n;
  cin>>n;
  int log=62;
  mint ans=0;
  auto f=[&](int k){
    vector dp(log+1,vector(log+1,vector<mint>(2)));
    dp[log][0][1]=1;
    for (int i=log-1;i>=0;i--){
      for (int p=0;p<=log;p++){
        for (int j:{0,1}){
          int np=p+j;
          if (np>log) continue;
          if (i==k&&j==0) continue;
          if ((n>>i&1)==j){
            dp[i][np][1]+=dp[i+1][p][1];
            dp[i][np][0]+=dp[i+1][p][0];
          }
          else if ((n>>i&1)<j){
            dp[i][np][0]+=dp[i+1][p][0];
          }
          else if ((n>>i&1)>j){
            dp[i][np][0]+=dp[i+1][p][0];
            dp[i][np][0]+=dp[i+1][p][1];
          }
        }
      }
    }
    mint cnt=0;
    for (int i=0;i<=log;i++){
      mint s=dp[0][i][0]+dp[0][i][1];
      cnt+=(s+1)*s/2;
    }
    ans+=(1LL<<k)*cnt;
  };
  for (int i=0;i<log;i++) f(i);
  cout<<ans.val()<<endl;
}

int main(){
  int t=1;
  while (t--) solve();
}
0