結果
問題 |
No.1952 xooooooooooor
|
ユーザー |
|
提出日時 | 2022-04-12 19:58:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,043 bytes |
コンパイル時間 | 2,355 ms |
コンパイル使用メモリ | 197,112 KB |
最終ジャッジ日時 | 2025-01-28 17:30:29 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include<bits/stdc++.h> using namespace std; long long modpow(long long a,long long b,long long mod){long long res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;} int main(){ constexpr long long mod=998244353; long long n,m;cin>>n>>m; long long n2=n; vector<int>bits; int sum=0; while(n){ bits.push_back(n&1); sum^=(n&1); n>>=1; } n=n2; reverse(bits.begin(),bits.end()); if(m<=(int)bits.size()){ long long ans=0; for(int i=0;i<m;i++)ans^=n*(1LL<<i); cout<<ans%mod<<endl; return 0; } vector<int>r(bits.size()),l(bits.size()); int tmp=0; for(int i=0;i<(int)bits.size();i++){ tmp^=bits[i]; r[i]=tmp; } tmp=0; for(int i=0;i<(int)bits.size();i++){ tmp^=bits[bits.size()-1-i]; l[i]=tmp; } long long ans=0; for(int i=0;i<(int)bits.size();i++){ ans+=l[i]*modpow(2,i,mod)%mod; ans+=r[i]*modpow(2,m+bits.size()-i-2,mod)%mod; ans%=mod; } if(sum)ans+=modpow(2,m-1,mod)-modpow(2,bits.size(),mod); ans=(ans+mod)%mod; cout<<ans<<endl; }