Submission #19372696


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;

int main(){
    int n, k;
    cin >> n >> k;

    map<int,int> table;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;

        if(table.find(a) == table.end()) table[a] = 0;
        table[a] += 1;
    }

    vector<long long int> pow2(n+1);
    pow2[0] = 1;
    for(int i=0; i<n; i++){
        pow2[i+1] = pow2[i] * 2;
        pow2[i+1] %= MOD;
    }

    int m = table.size();// < 500 since (1+500) * 500 / 2 > 1e5
    vector<vector<long long int>> dp(m+1,vector<long long int>(1<<17));
    dp[0][0] = 1;
    int i = 0;
    for(auto t : table){
        int x = t.first;
        int num = t.second;

        for(int j=0; j<(1<<17); j++){
            dp[i+1][j] += dp[i][j] * pow2[num-1];// nC0 + nC2 + ... = [(1+1)^n + (1+(-1))^n] / 2 = 2^{n-1}
            dp[i+1][j] %= MOD;

            assert(j^x < (1<<17));
            dp[i+1][j^x] += dp[i][j] * pow2[num-1];// nC1 + nC3 + ... = [(1+1)^n - (1+(-1))^n] / 2 = 2^{n-1}
            dp[i+1][j^x] %= MOD;
        }
        i += 1;
    }
    cout << dp[m][k] << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Limited Xor Subset
User probably
Language C++ (GCC 9.2.1)
Score 0
Code Size 1170 Byte
Status RE
Exec Time 356 ms
Memory 463944 KB

Compile Error

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from ./Main.cpp:1:
./Main.cpp: In function ‘int main()’:
./Main.cpp:37:24: warning: suggest parentheses around comparison in operand of ‘^’ [-Wparentheses]
   37 |             assert(j^x < (1<<17));
      |                      ~~^~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
RE × 3
RE × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt RE 112 ms 7396 KB
sample_02.txt RE 111 ms 6384 KB
sample_03.txt RE 113 ms 12376 KB
subtask_1_1.txt RE 116 ms 18488 KB
subtask_1_10.txt RE 123 ms 27656 KB
subtask_1_11.txt RE 125 ms 29844 KB
subtask_1_12.txt RE 120 ms 23860 KB
subtask_1_13.txt RE 122 ms 24756 KB
subtask_1_14.txt RE 119 ms 20692 KB
subtask_1_15.txt RE 116 ms 18512 KB
subtask_1_16.txt RE 115 ms 13488 KB
subtask_1_17.txt RE 112 ms 7440 KB
subtask_1_18.txt RE 119 ms 7784 KB
subtask_1_19.txt RE 114 ms 7600 KB
subtask_1_2.txt RE 119 ms 18576 KB
subtask_1_20.txt RE 353 ms 463944 KB
subtask_1_21.txt RE 356 ms 463768 KB
subtask_1_22.txt RE 112 ms 6200 KB
subtask_1_23.txt RE 111 ms 6280 KB
subtask_1_24.txt RE 109 ms 6344 KB
subtask_1_25.txt RE 124 ms 7060 KB
subtask_1_26.txt RE 109 ms 6340 KB
subtask_1_27.txt RE 114 ms 6356 KB
subtask_1_28.txt RE 113 ms 8152 KB
subtask_1_29.txt RE 111 ms 7328 KB
subtask_1_3.txt RE 120 ms 20600 KB
subtask_1_30.txt RE 112 ms 7404 KB
subtask_1_4.txt RE 118 ms 18500 KB
subtask_1_5.txt RE 118 ms 17720 KB
subtask_1_6.txt RE 117 ms 9700 KB
subtask_1_7.txt RE 120 ms 21584 KB
subtask_1_8.txt RE 163 ms 108000 KB
subtask_1_9.txt RE 246 ms 257180 KB