結果
問題 | No.2483 Yet Another Increasing XOR Problem |
ユーザー |
![]() |
提出日時 | 2023-09-22 22:08:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 1,210 bytes |
コンパイル時間 | 4,177 ms |
コンパイル使用メモリ | 253,756 KB |
最終ジャッジ日時 | 2025-02-17 00:41:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001int main(){long long m;cin>>m;if(m==1){cout<<1<<endl;return 0;}m--;mint ans = 0;int X = 0;rep(i,60){if((m>>i)&1)X = i;}ans += mint(2).pow(1LL<<X)-1;{mint v = mint(2).pow(m-(1LL<<X)+1)-1;v *= mint(2).pow(((1LL<<(X+1))-1)-m);ans +=v;}/*rep(i,1<<4){if(i==0)continue;int x = 0;if(((i>>0)&1)||((i>>1)&1))x++;if(((i>>2)&1)||((i>>1)&3))x++;if(x==1)ans--;}*/{vector<mint> dp(2);dp[0] = mint(2).pow((1LL<<X)-1);for(int i=X-1;i>=0;i--){vector<mint> ndp(2);int ss = ((m>>i))&1;rep(j,2){rep(k,2){rep(l,2){int tt = k^l;int jj = j;if(j==0 && tt>ss)continue;if(j==0&&tt<ss)jj = 1;mint v = dp[j];if(k){v *= mint(2).pow(1LL<<i);}if(l){v /= mint(2).pow(1LL<<i);}ndp[jj] += v;}}}swap(dp,ndp);}rep(i,2)ans += dp[i];}cout<<ans.val()<<endl;return 0;}