CF1815D 题解

· · 题解

UPD：更新了一个错误，感谢指出

更好的阅读体验

一道有趣的题。

首先发现 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, a_1\oplus a_2=2\times(b_1\oplus b_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 要么都是奇数，要么都是偶数，还是考虑分治，此时由于 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;
}