結果
問題 | No.1952 xooooooooooor |
ユーザー |
![]() |
提出日時 | 2022-05-20 22:28:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 926 bytes |
コンパイル時間 | 4,339 ms |
コンパイル使用メモリ | 255,168 KB |
最終ジャッジ日時 | 2025-01-29 10:57:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main() { int N,M; cin>>N>>M; int b = __builtin_popcount(N)%2; mint ans = b; if(M<=30){ b = 0; long long aa = 0; rep(i,M){ long long n = N; n <<= i; aa ^= n; } ans = aa; } else{ ans *= mint(2).pow(M+31)-1; set<int> S; rep(i,31){ S.insert(i); S.insert(M+30-i); } for(auto a:S){ if(a<=30){ int t = 0; for(int j=0;j<=a;j++){ t ^= (N>>j)&1; } if(t==0&&b==1)ans -= mint(2).pow(a); if(t==1&&b==0)ans += mint(2).pow(a); } else{ int t = 0; for(int j=M+30;j>=a;j--){ t ^= (N>>(j-(M-1)))&1; } if(t==0&&b==1)ans -= mint(2).pow(a); if(t==1&&b==0)ans += mint(2).pow(a); } } } cout<<ans.val()<<endl; return 0; }