1 条题解

  • 0
    @ 2026-4-5 18:21:32
    #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;
    }
    
    • 1

    信息

    ID
    467
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    133
    已通过
    39
    上传者