結果
問題 | No.2483 Yet Another Increasing XOR Problem |
ユーザー |
![]() |
提出日時 | 2023-09-22 23:03:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 2,066 bytes |
コンパイル時間 | 1,224 ms |
コンパイル使用メモリ | 130,824 KB |
最終ジャッジ日時 | 2025-02-17 01:01:19 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include<algorithm>#include<iostream>#include<string>#include<string.h>#include<array>#include<cmath>#include<iterator>#include<queue>#include<set>#include<map>#include<utility>#include<vector>#include<cfloat>#include<climits>#include<complex>#include<deque>#include<fstream>#include<functional>#include<iomanip>#include<list>#include<memory>#include<stack>#include<random>using namespace std;constexpr int mod = 998244353;long long modpow(long long a,long long b) {long long ans = 1;while(b) {if(b & 1) {(ans *= a) %= mod;}(a *= a) %= mod;b /= 2;}return ans;}int dp[66][2];void mpl(int &x,int y) {x += y;if(x >= mod) x -= mod;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);long long M;cin >> M;if(M == 1) {cout << 1 << "\n";return 0;}long long res = 0;for(int i = 60; i >= 0; i--) {if((1ll << i) >= M) {continue;}if((1ll << (i+1)) >= M) {dp[i][1] = 1;res = 1ll << i;}else {mpl(dp[i][0],dp[i+1][0]*(modpow(2,2ll << i))%mod);mpl(dp[i][0],dp[i+1][0]*(modpow(2,1ll << i))%mod);mpl(dp[i][0],dp[i+1][0]*(modpow(2,1ll << i))%mod);mpl(dp[i][0],dp[i+1][0]);if(1 & ((M-1) >> i)) {mpl(dp[i][1],dp[i+1][1]*(modpow(2,1ll << i))%mod*(modpow(2,1ll << i))%mod);mpl(dp[i][1],dp[i+1][1]);mpl(dp[i][0],dp[i+1][1]*(modpow(2,1ll << i))%mod);mpl(dp[i][0],dp[i+1][1]*(modpow(2,1ll << i))%mod);}else {mpl(dp[i][1],dp[i+1][1]*(modpow(2,1ll << i))%mod);mpl(dp[i][1],dp[i+1][1]*(modpow(2,1ll << i))%mod);}}}int ans = 0;mpl(ans,dp[0][0]);mpl(ans,dp[0][1]);mpl(ans,modpow(2,res));mpl(ans,modpow(2,2*res-M)*(modpow(2,M-res)+mod-1)%mod);mpl(ans,mod-1);cout << ans << "\n";}