传送门
题意：n(5e3)个数a1...an(>=0), a1^a2^...^an = 0, a1 + a2 +... + an = m(5e3),求数组ａ的个数
dp[i][j]代表前i位和为j的方案数
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int maxn = 5e3 + 5;
ll dp[20][maxn];
ll fac[maxn], inv[maxn];
ll n, m;
ll qpow(ll x, ll y)
{ll res = 1;while(y){if(y & 1) res = res * x % mod;x = x * x % mod;y >>= 1;}return res;
}
void init()
{fac[0] = 1;for(int i = 1; i <= 5000; ++i) fac[i] = i * fac[i - 1] % mod;inv[5000] = qpow(fac[5000], mod - 2);for(int i = 5000 - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(ll n, ll m)
{if(n < m) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{cin >> n >> m;init();for(int i = 0; i <= m; ++i){dp[0][i] = (i <= n && i % 2 == 0) * C(n, i) % mod;}for(int i = 1; i <= 12; ++i){for(int j = 0; j <= m; ++j){for(int k = 0; j - k * (1 << i) >= 0; k += 2){dp[i][j] = (dp[i][j] + dp[i - 1][j - k * (1 << i)] * C(n, k) % mod) % mod;}}}cout << dp[12][m] << endl;
}