結果

問題 No.1456 Range Xor
ユーザー ethan_h
提出日時 2021-03-31 21:19:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,362 bytes
コンパイル時間 2,362 ms
コンパイル使用メモリ 171,176 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-15 14:15:55
合計ジャッジ時間 8,833 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 6 RE * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

//ethan_h
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*void test(){
int n;cin>>n;
string s;cin>>s;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];}

}
*/
int subsetXOR(vector<int>arr, int n, int k)
{
    // Find maximum element in arr[]
    int max_ele = arr[0];
    for (int i=1; i<n; i++)
       if (arr[i] > max_ele)
           max_ele = arr[i];

    // Maximum possible XOR value
    int m = (1 << (int)(log2(max_ele) + 1) ) - 1;
    if( k > m  )
       return 0;
    // The value of dp[i][j] is the number of subsets having
    // XOR of their elements as j from the set arr[0...i-1]
    int dp[n+1][m+1];

    // Initializing all the values of dp[i][j] as 0
    for (int i=0; i<=n; i++)
        for (int j=0; j<=m; j++)
            dp[i][j] = 0;

    // The xor of empty subset is 0
    dp[0][0] = 1;

    // Fill the dp table
    for (int i=1; i<=n; i++)
        for (int j=0; j<=m; j++)
            dp[i][j] = dp[i-1][j] + dp[i-1][j^arr[i-1]];

    //  The answer is the number of subset from set
    //  arr[0..n-1] having XOR of elements as k
    return dp[n][k];
}
int main(){
ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

//int t;cin>>t;
int n,k;cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++){
    cin>>a[i];
}
int res;
res=subsetXOR(a,n,k);
if(res>0){
    cout<<"Yes";
}
else{
    cout<<"No";
}
return 0;}
0