Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MOD 1000000007
- using namespace std;
- int arr[100000];
- int dp[100001][128][2];
- int desired;
- int n;
- int solve(int i,int curr,bool empty) {
- if(i == n)
- return curr == 0;
- if(dp[i][curr][empty] != -1)
- return dp[i][curr][empty];
- return dp[i][curr][empty] = (solve(i+1,curr,empty) + solve(i+1,curr^arr[i],empty)) % MOD;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i = 0;i<n;i++)
- scanf("%d",&arr[i]);
- memset(dp,-1,sizeof dp);
- long long ans = 0;
- for(int i = 0;i<128;i++) {
- solve(0,i,true);
- }
- dp[0][0][1]--;
- for(int i = 0;i<128;i++) {
- long long first = dp[0][i][1];
- long long second = dp[0][i][1] -1;
- if(first % 2 == 0)
- first /= 2;
- else
- second /= 2;
- ans = (ans + first*second % MOD ) % MOD;
- }
- // dp[1][0] = 1;
- // dp[1][arr[0]] = 1;
- // for (int i=2; i<=n; i++)
- // for (int j=0; j<256; j++)
- // dp[i][j] = (dp[i-1][j] + dp[i-1][j^arr[i-1]])%MOD;
- //
- // long long ans = 0;
- // dp[n][0]--;
- // for(int i = 0;i<256;i++) {
- // long long first = dp[n][i];
- // long long second = dp[n][i] -1;
- // if(first % 2 == 0) {
- // first /= 2;
- // } else {
- // second /= 2;
- // }
- //
- // ans = (ans + first * second % MOD) % MOD;
- // }
- cout<<ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement