結果
問題 | No.2483 Yet Another Increasing XOR Problem |
ユーザー |
![]() |
提出日時 | 2023-09-24 17:42:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 3,345 ms |
コンパイル使用メモリ | 253,932 KB |
最終ジャッジ日時 | 2025-02-17 02:10:18 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using mint = modint998244353;const int mod = 998244353;//using mint = modint1000000007;//const int mod = 1000000007;//const int INF = 1e9;//const long long LINF = 1e18;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define endl "\n"#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }mint f(int t, int u, int k) {// t-t^uの箇所// if:0 == u -> 1;// elif 0 == t ->2^(-k);// else -> 2^kmint tw = 2;if (0 == u)return 1;else if (1 == t)return tw.pow(1LL << k);else return tw.pow(1LL << k).inv();}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);long long m; cin >> m;int k = 0;while ((1LL << (k + 1)) <= m) k++;mint ans = 0;// 0000000000ans += ((mint)2).pow(1LL << k) - 1;// 1000000000ans += ((mint)2).pow(1LL << k) - ((mint)2).pow((1LL << k) * 2 - m);/*全てのt∈[0,2^k)u∈[0,m-2^k)に対しての(mint)2.pow(t+(1<<k)-1-(t^u))の総和すなわち2^(t-(t^u))について考える*/m = m - (1LL << k);vector<mint> dp(2);dp[0] = 1;rrep(i, k) {vector<mint> ndp(2);int u = 1 & (m >> i);// 0->0rep(t, 2) ndp[0] += dp[0] * f(t, u, i);// 0->1if (u) rep(t, 2) ndp[1] += dp[0] * f(t, 0, i);// 1->1rep(t, 2)rep(u, 2) ndp[1] += dp[1] * f(t, u, i);swap(dp, ndp);}ans += dp[1] * mint(2).pow((1LL << k) - 1);cout << ans.val() << endl;return 0;}