题解：AT_arc227_e [ARC227E] Shift and XOR Switches

· · 题解

首先考虑做两次操作，间隔分别为 x,y：

\begin{aligned} B_i'&= B_i\oplus B_{i-x}\\ B_i''&=B_i'\oplus B_{i-y}'\\ B_i&=B_i\oplus B_{i-x}\oplus B_{i-y}\oplus B_{i-x-y} \end{aligned}

观察这个式子，发现操作顺序不重要。

思考操作序列满足什么条件时 B 序列不一样。考虑对于两个没有相同元素的操作序列 X,Y（因为有相同元素显然不会让 B 不同），则取两个操作序列里最小元素考虑，也就可以得出当集合无重复元素的时候 B 一定不同，因为第一个 1 位置不同（如果有重复元素则可能会因为操作偶数次而消去）。

那么接下来只要考虑重复元素对操作序列的影响了，套一下上面的式子，得到：

B_i=B_i\oplus B_{i-2\times x}

也就是操作两次 x 相当于操作一次 2\times x。

进一步想到可以依据每个数除去 2 的幂次后划分成若干个类，而且类间方案互不干扰。

对于一个类内的一个数字设其质因数分解后 2 的幂次为 k，则相当于这里类内可以做一次 2^k 的操作（不同于题目中的操作，是用来区分类内不同方案的）。

而我们希望通过这样一些操作最后凑出的等价操作集合不同，也就相当于操作的 \sum 2^k 二进制不同，于是数位 DP 统计即可。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N = 200005, mod = 998244353;
int n, m, a[N];
map <int, bool> mp;
long long ans = 1;
int dick(int x){
    while(!(x & 1)){
        x >>= 1;
    }
    return x;
}
inline int add(int x, int y){
    x += y;
    if(x >= mod)x -= mod;
    return x;
}
int dfs(int p, int num){
    if(p >= n)return 1;
    int c = num + a[p];
    int res = dfs(p << 1, c >> 1);
    if(c)res = add(res, dfs(p << 1, c - 1 >> 1));
    return res;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= m;i++){
        int x;scanf("%d", &x);
        a[x]++;mp[dick(x)] = 1;
    }
    for(auto t : mp){
        int p = t.first;
        ans = ans * dfs(p, 0) % mod;
    }
    printf("%lld", ans);
    return 0;
}