yukicoder No.183 たのしい排他的論理和(EASY)
yukicoder No.183 たのしい排他的論理和(EASY)
問題概要
リンク参照
考察
- dp[i]:=整数iを作れるか(作れる場合は1)とし,dp[0]=1で初期化
- dp[j]==1の場合はdp[j^A[i]]=1と遷移できる(配列外参照に注意)
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; int dp[1<<16]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); int maxi = 0; int X = 0; for (int i = 0; i < N; i++) { cin >> A[i]; } dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = (1 << 15); j >= 0; j--) { if (dp[j] == 0)continue; dp[j ^ A[i]] = 1; } } int sum = 0; for (int i = 0; i < (1 << 15); i++) { sum += dp[i]; } cout << sum << endl; }