fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. // For all linux platforms!
  7. typedef long long __int64;
  8.  
  9. const int mod = 1000000003;
  10. int result, ope[55], xorv[55][35]; bool valid[35];
  11. int dp[55][35][2];
  12.  
  13. int main ()
  14. {
  15.     int n; while (scanf("%d %d", &n, &result), n)
  16.     {
  17.         for (int i = 1; i <= n; i++) scanf("%d", &ope[i]), ++ope[i];
  18.         for (int i = 0; i < 31; i++) xorv[0][i] = 0;
  19.         for (int i = 1; i <= n; i++)
  20.         {
  21.             for (int j = 0; j < 31; j++)
  22.                 xorv[i][j] = xorv[i - 1][j] ^ (ope[i] & (1 << j));
  23.         }
  24.         valid[31] = true;
  25.         for (int i = 30; i >= 0; i--) valid[i] = valid[i + 1] && (xorv[n][i] == (result & (1 << i)));
  26.         memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
  27.         for (int i = 1; i <= n; i++)
  28.         {
  29.             for (int j = 0; j < 31; j++) for (int s = 0; s < 2; s++)
  30.             {
  31.                 if (dp[i - 1][j][s] == 0) continue;
  32.                 for (int k = 0; k < 31; k++) if (ope[i] & (1 << k))
  33.                 {
  34.                     int free, tj, ts;
  35.                     if (k > j) free = j, tj = k, ts = (xorv[i - 1][k] ? 1 : 0);
  36.                     else
  37.                     {
  38.                         int tm = (k == j ? 0 : ope[i] & (1 << j));
  39.                         free = k, tj = j, ts = s ^ (tm ? 1 : 0);
  40.                     }
  41.                     dp[i][tj][ts] = ((__int64)dp[i - 1][j][s] * (1 << free) + dp[i][tj][ts]) % mod;
  42.                 }
  43.             }
  44.         }
  45.         int ans = 0;
  46.         for (int i = 30; i >= 0; i--)
  47.         {
  48.             if (valid[i + 1]) ans = (ans + dp[n][i][(result & (1 << i)) ? 1 : 0]) % mod;
  49.             else break;
  50.         }
  51.         printf("%d\n", ans);
  52.     }
  53.     return 0;
  54. } 
  55.  
stdin
copy 
11 2047
1024 512 256 128 64 32 16 8 4 2 1
10 2047
1024 512 256 128 64 32 16 8 4 2 
0 0
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
1
0
https://ideone.com/4CRTe
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!