CF1815D XOR Counting DP + 分治

给定 $n,m$ ，求长度为 $m$ 的序列 $a$ 且满足 ∑ a i = n \sum a_i=n ∑ai​=n 的所有可能异或值之和

n ≤ 1 0 18 , m ≤ 1 0 5 n \le 10^{18}, m \le 10^5 n≤1018,m≤105

• 这个 m ≤ 1 0 5 m \le 10^5 m≤105 比较迷惑人，所以一上来可以往 $dp$ 方面去想，结果可以发现当 $m\ge 3$ 时，一定可以构造出所有与 $n$ 同奇偶性的数，$m=1$ 时结论显然。

• 考虑 $m=2$ ，情况变得比较好做：

  • 如果 $n$ 是奇数，那么一定是一奇一偶，钦定 $a$ 是奇数，那么记 a ′ = a − 1 2 , b ′ = b 2 a'=\frac{a-1}{2},b'=\frac{b}{2} a′=2a−1​,b′=2b​ ，此时

    • a ⊕ b = 2 ( a ′ ⊕ b ′ ) + 1 a\oplus b=2(a'\oplus b') +1 a⊕b=2(a′⊕b′)+1

    • a ′ + b ′ = n − 1 2 a'+b'= \frac{n-1}{2} a′+b′=2n−1​

    • 定义 f n f_n fn​ 表示答案的和， g n g_n gn​ 表示答案个数，奇数情况转移即：

    • g n = g n − 1 2 f n = 2 × f n − 1 2 + g n g_n = g_{\frac{n-1}{2}} \\ f_n = 2 \times f_{\frac{n-1}{2}} +g_n gn​=g2n−1​​fn​=2×f2n−1​​+gn​

  • 偶数情况：

    • 记 a ′ = a 2 , b ′ = b 2 a'=\frac{a}{2},b'=\frac{b}{2} a′=2a​,b′=2b​ ，则 a ⊕ b = 2 ( a ′ ⊕ b ′ ) a\oplus b=2(a'\oplus b') a⊕b=2(a′⊕b′) ， a ′ + b ′ = n 2 a'+b'= \frac{n}{2} a′+b′=2n​

    • 或 a ′ = a − 1 2 , b ′ = b − 1 2 a'=\frac{a-1}{2},b'=\frac{b-1}{2} a′=2a−1​,b′=2b−1​ ，则 a ⊕ b = 2 ( a ′ ⊕ b ′ ) a\oplus b=2(a'\oplus b') a⊕b=2(a′⊕b′) ， a ′ + b ′ = n 2 − 1 a'+b'= \frac{n}{2}-1 a′+b′=2n​−1

    • g n = g n 2 + g n 2 − 1 f n = 2 × ( f n 2 + f n 2 − 1 ) g_n = g_{\frac{n}{2}}+g_{\frac{n}{2}-1}\\ f_n = 2 \times (f_{\frac{n}{2}}+f_{\frac{n}{2}-1}) gn​=g2n​​+g2n​−1​fn​=2×(f2n​​+f2n​−1​)

• 时间复杂度 $O(logn)$

#include
using namespace std;typedef long long ll;
const ll mo=998244353;map<ll,ll > f,g;void dfs(ll x) {if(g[x]) return ;if(!x) {f[x]=0, g[x]=1;return ;}if(x&1) {dfs(x/2);f[x]=(2*f[x/2]+g[x/2])%mo;g[x]=g[x/2];}else {dfs(x/2), dfs(x/2-1);g[x]=(g[x/2]+g[x/2-1])%mo;f[x]=2*(f[x/2]+f[x/2-1])%mo;}return ;
}void solve() {ll n,m; cin>>n>>m;if(m>=3) {if(n&1) cout<<(n/2+1)%mo*((n/2+1)%mo)%mo<<'\n';else cout<<(n/2+1)%mo*((n/2)%mo)%mo<<'\n';} else if(m==1) cout<<n%mo<<'\n';else {dfs(n);cout<<f[n]<<'\n';}return ;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll t; cin>>t;while(t--) solve();return 0;
}