1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define ll long long int n, x; int a[100005]; const int mod = 998244353; int main() { cin >> n >> x;//分别为数组长度和目标异或值 for (int i = 1; i <= n; i++)cin >> a[i]; vector<int> dp(64, 0);//从前i个物品中选取若干个元素异或结果为x的方案数,降维实现 //初始化 dp[0] = 1; //不选的话异或结果默认为0,为一种方案 for (int i = 1; i <= n; i++) {//枚举前i个数 vector<int> last = dp; //记录下上一层的dp结果因为递推过程会改变上一层结果 for (int j = 0; j <= 63; j++) {//枚举上一层异或的值 int num = a[i];//要异或的数 //下一层异或的结果为j^num对应改变:包含上一层为j^num和上一层为j然后本层异或num两种情况 dp[j ^ num] = (last[j ^ num] + last[j]) % mod; } } cout << dp[x]; return 0; }
信息
- ID
- 467
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 133
- 已通过
- 39
- 上传者