E - Team Combinations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君はプログラミング合宿の幹事を務めています。合宿の参加者はあらかじめ第 1 グループと第 2 グループの 2 つに分かれており、各グループにはそれぞれ N 人のメンバーがいます。

各メンバーには非負整数のスキル値が割り当てられています。第 1 グループのメンバーのスキル値は A_1, A_2, \ldots, A_N 、第 2 グループのメンバーのスキル値は B_1, B_2, \ldots, B_N です。異なるメンバーが同じスキル値を持つこともあります。

高橋君は、各グループからそれぞれメンバーの部分集合を 1 つずつ選びます（空集合、すなわち誰も選ばないことも許されます）。第 1 グループから選んだメンバーのスキル値の XOR（排他的論理和）を X 、第 2 グループから選んだメンバーのスキル値の XOR を Y とします。グループから誰も選ばなかった場合、そのグループの XOR は 0 とします。

青木君から、合宿の課題として非負整数の目標値 S が伝えられました。チーム編成が成功する条件は、X + Y = S を満たすことです。ここでの + は通常の整数の加算です。

第 1 グループからの部分集合の選び方と第 2 グループからの部分集合の選び方の組を 1 つの 選び方の組 とします。選ばれるメンバーの部分集合が少なくとも一方のグループで異なれば、結果として同じ X, Y の値になったとしても、それらは異なる選び方の組として別々に数えます。

X + Y = S を満たすような選び方の組の個数を求めてください。

制約

  • 1 \leq N \leq 50
  • 0 \leq S < 2^{21}
  • 0 \leq A_i < 2^{20} (1 \leq i \leq N)
  • 0 \leq B_i < 2^{20} (1 \leq i \leq N)
  • 入力はすべて整数である
  • 答えは 2^{63} 未満であることが保証される

入力

N S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • 1 行目には、各グループのメンバー数を表す整数 N と、目標値を表す整数 S が、スペース区切りで与えられる。
  • 2 行目には、第 1 グループの N 人のスキル値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、第 2 グループの N 人のスキル値を表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

条件 X + Y = S を満たす選び方の組の個数を 1 行で出力せよ。

入力例 1

2 3
1 2
0 3

出力例 1

4

入力例 2

2 7
1 2
8 16

出力例 2

0

入力例 3

10 12345
0 1 2 3 5 8 13 21 34 55
7 7 14 28 56 112 224 448 896 1792

出力例 3

0

入力例 4

40 1048576
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 262145 524289 1048575
524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 6 10 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152 98304 196608 393216 786432 1048574

出力例 4

1152920405095219200

入力例 5

1 2097150
1048575
1048575

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is organizing a programming camp. The participants of the camp are already divided into two groups, Group 1 and Group 2, each consisting of N members.

Each member has a non-negative integer skill value assigned. The skill values of the members in Group 1 are A_1, A_2, \ldots, A_N, and the skill values of the members in Group 2 are B_1, B_2, \ldots, B_N. Different members may have the same skill value.

Takahashi will choose a subset of members from each group (the empty set, i.e., choosing no one, is also allowed). Let X be the XOR (bitwise exclusive OR) of the skill values of the members chosen from Group 1, and Y be the XOR of the skill values of the members chosen from Group 2. If no one is chosen from a group, the XOR for that group is 0.

Aoki has given him a non-negative integer target value S as a task for the camp. The condition for successful team formation is that X + Y = S is satisfied. Here, + represents standard integer addition.

A pair consisting of a choice of a subset from Group 1 and a choice of a subset from Group 2 is called a combination of choices. If the chosen subset of members differs in at least one group, they are counted as different combinations of choices, even if they result in the same values of X and Y.

Find the number of combinations of choices that satisfy X + Y = S.

Constraints

  • 1 \leq N \leq 50
  • 0 \leq S < 2^{21}
  • 0 \leq A_i < 2^{20} (1 \leq i \leq N)
  • 0 \leq B_i < 2^{20} (1 \leq i \leq N)
  • All input values are integers.
  • The answer is guaranteed to be less than 2^{63}.

Input

N S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • The first line contains an integer N, representing the number of members in each group, and an integer S, representing the target value, separated by a space.
  • The second line contains N integers A_1, A_2, \ldots, A_N, representing the skill values of the members of Group 1, separated by spaces.
  • The third line contains N integers B_1, B_2, \ldots, B_N, representing the skill values of the members of Group 2, separated by spaces.

Output

Print the number of combinations of choices that satisfy the condition X + Y = S in a single line.

Sample Input 1

2 3
1 2
0 3

Sample Output 1

4

Sample Input 2

2 7
1 2
8 16

Sample Output 2

0

Sample Input 3

10 12345
0 1 2 3 5 8 13 21 34 55
7 7 14 28 56 112 224 448 896 1792

Sample Output 3

0

Sample Input 4

40 1048576
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 262145 524289 1048575
524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 6 10 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152 98304 196608 393216 786432 1048574

Sample Output 4

1152920405095219200

Sample Input 5

1 2097150
1048575
1048575

Sample Output 5

1