思路
因为题目与二进制有关,考虑往二进制的方向思考。定义 \(dp_{i,j}\) 表示在所有的 \(n\) 个数中,当前在决策对于每一个数在二进制表示下的第 \(i\) 位是 \(0\) 还是 \(1\),且和为 \(j\) 的方案数。
因为异或需要满足对于所有 \(a_i\) 表示为二进制后每一位 \(1\) 的个数均为偶数。所以在所有数中第 \(i\) 位出现 \(1\) 的数量必须是偶数。
那么,我们还可以枚举一个 \(k\) 表示所有数中第 \(i\) 位选 \(1\) 的数量,得到状态转移方程:
\[ dp_{i,j} = \sum_{k = 0}^{j \geq k \times 2^i}(dp_{i - 1,j - k \times 2^i} \times \binom{n}{k}) \]时间复杂度为 \(\Theta(m \log^2{m})\)。
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 5010,M = 15,mod = 998244353;
int n,m;
int mul[N],inv[N];
int dp[M + 10][N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int Add(int a,int b){
return (a + b) % mod;
}
inline int Sub(int a,int b){
return ((a - b) % mod + mod) % mod;
}
inline int Mul(int a,int b){
return a * b % mod;
}
inline int exgcd(int a,int b,int &x,int &y){
if (!b){
x = 1;
y = 0;
return a;
}
int d = exgcd(b,a % b,y,x);
y = y - a / b * x;
return d;
}
inline int get_inv(int a,int p){
int x,y;
exgcd(a,p,x,y);
return (x % mod + mod) % mod;
}
inline void init(){
mul[0] = 1;
for (re int i = 1;i <= n;i++) mul[i] = Mul(mul[i - 1],i);
inv[n] = get_inv(mul[n],mod);
for (re int i = n - 1;~i;i--) inv[i] = Mul(inv[i + 1],(i + 1));
}
inline int C(int n,int m){
if (n < m) return 0;
return Mul(mul[n],Mul(inv[m],inv[n - m]));
}
signed main(){
n = read();
m = read();
init();
for (re int i = 0;i <= m;i += 2) dp[0][i] = C(n,i);
for (re int i = 1;i <= M;i++){
for (re int j = 0;j <= m;j++){
int k = 0;
while (j >= k * (1ll << i)){
dp[i][j] = Add(dp[i][j],Mul(dp[i - 1][j - k * (1ll << i)],C(n,k)));
k += 2;
}
}
}
printf("%lld",dp[M][m]);
return 0;
}
标签:ARC116D,arc116,int,题解,times,二进制,dp
From: https://www.cnblogs.com/WaterSun/p/18263294