TopCoder SRM 564 - 850: DefectiveAddition

Problem Statement

题目简述

给定一个序列A和一个整数n，
要求构造一个长度与原序列相同的序列B，
对于每个位置i，要求0<=B[i]<=A[i]，且序列B的异或和为n。求方案数（模1e9+7）。

0 <= n, A[i] <= 10^9
len <= 50

Cucumber Boy is very young. He is too young for base 10, so he does all his calculations in base 2. Additionally, he did not learn to add yet. When adding two numbers, he always forgets to do the carries, he just adds each digit independently. As you probably guessed already, the result of his calculation is in fact the bitwise xor of the two input numbers. For example, for Cucumber Boy 1+1 is 0, 1+2 is 3, 2+3 is 1, and 4+7 is 3. (All the numbers in this example are in base 10.)

Cucumber Boy has a sequence of cards. Each card contains a positive integer. You are given a int[] cards containing those integers.

You are also given a int n. Cucumber Boy wants to choose a sequence of integers b with the following properties:

For each i, the integer b[i] is greater than or equal to 0.
For each i, the integer b[i] is less than or equal to cards[i].
The "Cucumber Boy sum" (i.e., the bitwise xor) of all elements of the sequence b is equal to n.

Return the number of such sequences, modulo 1,000,000,007.

Test cases

input
- cards { 2, 3 }
- n 2
output
Returns 3

note

Cucumber Boy can choose 12 different sequences: b[0] can be between 0 and 2, inclusive, and b[1] can be between 0 and 3, inclusive.

Out of those 12 sequences, 3 have the required "Cucumber Boy sum": 0+2 = 2, 1+3 = 2, and 2+0 = 2.
input
- cards { 1, 2, 3 }
- n 1
output
Returns 6

note

The six good sequences are (0,0,1), (0,1,0), (0,2,3), (1,0,0), (1,1,1), and (1,2,2).
input
- cards { 4, 5, 7, 11 }
- n 6
output
Returns 240
input
- cards { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
- n 15
output
Returns 1965600
input
- cards { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
- n 16
output
Returns 0
input
- cards { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
- n 1
output
Returns 949480669

back to the menu

SRM 564 1 850 DefectiveAddition

Problem Statement

Definition

Limits

Constraints

Test cases