题目本质就是对一个多项式 \(F\) 进行等比数列求和得到 \(G\)（\(F_i\) 表示 \(i\) 在序列 \(A\) 中的出现次数），求 \(G\) 所有下标 \(>0\) 的位置的权值和。
显然，\(M\) 固定就可以直接做了。但 \(M\) 不固定，所以我们只能暴力枚举 \(M\) 并进行 \(N\) 次 FWT 卷积。复杂度显然不满足需求。
容易想到一个经典的套路就是，我们可以直接对点值进行操作。于是我们 FWT 完后对所有点值进行等比数列求和，再 IFWT 回去就行了。
值得一提的是，在实现对点值的等比数列求和时，需特判点值为 \(1\) 的情况。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
constexpr int N = 1 << 16 + 10;
constexpr ll mod = 998244353, inv2 = (mod + 1) >> 1;
int n = 1 << 16, m, k; ll ans, a[N];
ll Pow(ll a, ll b){
ll ans = 1;
while(b){
if(b & 1) (ans *= a) %= mod;
(a *= a) %= mod, b >>= 1;
}
return ans;
}
void FWT_xor(ll f[], ll x = 1){
for(int b = 2, k = 1; b <= n; b <<= 1, k <<= 1){
for(int i = 0; i < n; i += b){
for(int j = 0; j < k; ++j){
f[i + j] += f[i + j + k];
f[i + j + k] = f[i + j] - f[i + j + k] * 2 % mod + mod;
(f[i + j] *= x) %= mod, (f[i + j + k] *= x) %= mod;
}
}
}
}
int main(){
scanf("%d%d", &k, &m);
FL(i, 1, m){int x; scanf("%d", &x), ++a[x];}
FWT_xor(a);
FL(i, 0, n - 1){
if(a[i] == 1) a[i] = k;
else a[i] = ((Pow(a[i], k + 1) + mod - 1) * Pow(a[i] + mod - 1, mod - 2) + mod - 1) % mod;
}
FWT_xor(a, inv2);
FL(i, 1, n - 1) ans += a[i];
printf("%lld\n", (ans % mod + mod) % mod);
return 0;
}