CF1816F Xor Counting - dp - 分治 -

题目链接：https://codeforces.com/contest/1816/problem/F

题解：
一道有趣的题。

• 首先发现 \(m=1\) 和 \(m\geq 3\) 时结论是平凡的。\(m=1\) 时结论显然，下面讨论一下 \(m\geq 3\) 时：
  首先可以构造 \([x, (n-x)/2, (n-x)/2, \cdots]\)，其中 \(x\) 和 \(n\) 同奇偶，显然此时异或值可以取到 \(1\cdots n\) 的所有和 \(n\) 奇偶性相同的值。另一方面，一个重要观察是 \(a_1 \oplus \cdots \oplus a_n\) 的奇偶性和 \(a_1+\cdots+a_n\) 相同，因此异或值至多取到所有和 \(n\) 奇偶性相同的值。因此这块可以 \(O(1)\) 求出。
• 下面我们讨论一下 \(m=2\) 的情况。
  设 \(f_n\) 表示 \(a_1+a_2=n\) 时的答案，考虑分治：
  如果 \(n\) 为奇数，那么 \(a_1, a_2\) 一奇一偶，不失一般性设 \(a_1, a_2\) 分别为奇数 偶数，如果令 \(b_1=(a_1-1)/2, b_2=a_2/2\)，那么 \(b_1+b_2=(n-1)/2, b_1\oplus b_2=2\times(a_1\oplus a_2)+1\)，因此我们还需要记一个 \(g_n\) 表示有多少种不同的异或值（因为这个 +1 是对于所有不同的异或值都要算的），\(g_n\) 此时的转移也很简单。综上我们有 \(n\) 为奇数时 \(f_n=2\times f_{n/2-1}+g_{n}\) 以及 \(g_n=g_{(n-1)/2}\)
  如果 \(n\) 为偶数，那么 \(a_1, a_2\) 要么都是奇数，要么都是偶数，还是考虑 /2 分治，此时由于 \(n\) 奇数，所以没有 +1 的项，因此和上一种情况完全相同的推导我们有 \(f_n=2\times (f_{n/2}+f_{n/2-1})\) 以及 \(g_n=g_{n/2}+g_{n/2-1}\)。

直接递推实现即可，复杂度 \(O(\log n)\)。
代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod = 998244353;

map<ll,ll>f,g;
void solve(ll n){
	if(n == 0){
		f[n] = 0, g[n] = 1;
		return ;
	}
	if(f.count(n))return ;
	if(n%2 == 1){
		solve(n/2);
		(f[n] = 2ll*f[n/2]%mod + g[n/2])%=mod;
		g[n] = g[n/2];
	}else{
		solve(n/2);solve(n/2-1);
		f[n] = 2ll * (f[n/2] + f[n/2-1]) % mod;
		g[n] = (g[n/2] + g[n/2-1]) % mod;
	}
}

signed main(){
	int te;scanf("%d",&te);
	while(te --){
		f.clear(), g.clear();
		ll n,m;cin >> n >> m;
		if(m == 1){
			cout << n%mod << '\n';
		}else if(m >= 3){
			if(n%2 == 1)cout << (n+1)/2%mod*((n+1)/2%mod)%mod << '\n';
			else cout << (1+n/2%mod)*(n/2%mod) % mod << '\n';
		}else{
			solve(n);
			cout << f[n] << '\n';
		}
	}

	return 0;
}