Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MOD 1000000007
  3. using namespace std;
  4.  
  5. int arr[100000];
  6. int dp[100001][128][2];
  7. int desired;
  8. int n;
  9.  
  10. int solve(int i,int curr,bool empty) {
  11. if(i == n)
  12. return curr == 0;
  13.  
  14. if(dp[i][curr][empty] != -1)
  15. return dp[i][curr][empty];
  16.  
  17. return dp[i][curr][empty] = (solve(i+1,curr,empty) + solve(i+1,curr^arr[i],empty)) % MOD;
  18. }
  19.  
  20. int main()
  21. {
  22. scanf("%d",&n);
  23. for(int i = 0;i<n;i++)
  24. scanf("%d",&arr[i]);
  25. memset(dp,-1,sizeof dp);
  26. long long ans = 0;
  27. for(int i = 0;i<128;i++) {
  28. solve(0,i,true);
  29. }
  30. dp[0][0][1]--;
  31. for(int i = 0;i<128;i++) {
  32. long long first = dp[0][i][1];
  33. long long second = dp[0][i][1] -1;
  34. if(first % 2 == 0)
  35. first /= 2;
  36. else
  37. second /= 2;
  38.  
  39. ans = (ans + first*second % MOD ) % MOD;
  40. }
  41.  
  42. // dp[1][0] = 1;
  43. // dp[1][arr[0]] = 1;
  44. // for (int i=2; i<=n; i++)
  45. // for (int j=0; j<256; j++)
  46. // dp[i][j] = (dp[i-1][j] + dp[i-1][j^arr[i-1]])%MOD;
  47. //
  48. // long long ans = 0;
  49. // dp[n][0]--;
  50. // for(int i = 0;i<256;i++) {
  51. // long long first = dp[n][i];
  52. // long long second = dp[n][i] -1;
  53. // if(first % 2 == 0) {
  54. // first /= 2;
  55. // } else {
  56. // second /= 2;
  57. // }
  58. //
  59. // ans = (ans + first * second % MOD) % MOD;
  60. // }
  61. cout<<ans;
  62.  
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement