Jolly Jumpers..~

Problem Statement
     
Let us introduce a new operation called double xor, and use the operator ^^ to denote it. For two integers A and B, A ^^ B is calculated as follows. Take the decimal representations of A and B. If they have different lengths, prepend the shorter one with leading zeros until they both have the same length. Then, label the digits of A as a1, a2, …, an (from left to right) and the digits of B as b1, b2, ... , bn (from left to right). C = A ^^ B will consist of the digits c1, c2, ... , cn (from left to right), where ci = (ai ^ bi) % 10, where ^ is the usual bitwise XOR operator (see notes for exact definition) and x % y is the remainder of x divided by y. If C happens to have any extra leading zeroes, they are ignored. For example, 8765 ^^ 2309 = 462 (c1 = (8 ^ 2) % 10 = 10 % 10 = 0, c2 = (7 ^ 3) % 10 = 4 % 10 = 4, c3 = (6 ^ 0) % 10 = 6 % 10 = 6, c4 = (5 ^ 9) % 10 = 12 % 10 = 2), and 5 ^^ 123 = 126 ("5" is prepended with two leading zeros to become "005"). When multiple ^^ operations occur in an expression, they must be evaluated from left to right. For example, A ^^ B ^^ C means (A ^^ B) ^^ C. You are given an int N. Return the value of N ^^ (N - 1) ^^ (N - 2) ^^ … ^^ 1.
Definition
   
Class:
DoubleXor
Method:
calculate
Parameters:
int
Returns:
int
Method signature:
int calculate(int N)
(be sure your method is public)
   
 
Notes
-
If a and b are single bits then a ^ b is defined as (a + b) % 2. For two integers, A and B, in order to calculate A ^ B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A ^ B = C = (cn...c1)2, where ci = ai ^ bi. For example, 10 ^ 3 = (1010)2 ^ (0011)2 = (1001)2 = 9.
Constraints
-
N will be between 1 and 1,000,000, inclusive.
Examples
0)
 
   
1
Returns: 1
This is simply 1.
1)
 
   
2
Returns: 3
2^^1=3
2)
 
   
7
Returns: 0
7^^6^^5^^4^^3^^2^^1=0
3)
 
   
10
Returns: 11
 
4)
 
   
102
Returns: 103
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
You have a piece of paper with exactly D positions laid out in a horizontal row. Each position looks like the following:
 _
|_|
|_|
 
 
There are 7 line segments in each position, and each line segment can hold exactly one match. Matches cannot be placed anywhere except on the line segments. You are given an integer N containing exactly D digits (with no leading zeroes). Spell out the number using matches on the paper. Each digit must occupy a single position. The following diagram shows how each digit should be formed:
      _                _        _                 _       _        _        _        _
 0 - | |  1 -  |  2 -  _|  3 -  _|  4 - |_|  5 - |_  6 - |_   7 -   |  8 - |_|  9 - |_|
     |_|      _|      |_        _|        |       _|     |_|        |      |_|       _|
 
 
After you lay out the initial arrangement, you are allowed to move up to K matches. You cannot discard matches or add new matches. After you make all your moves, the final arrangement must be valid (as described above) and the integer formed by the arrangement must contain the same number of digits as the original integer. Leading zeroes are allowed. Return the number of distinct integers that can be formed in this manner. Note that the original integer counts toward the total because it always obtainable by making 0 moves.
Definition
   
Class:
NumbersAndMatches
Method:
differentNumbers
Parameters:
long long, int
Returns:
long long
Method signature:
long long differentNumbers(long long N, int K)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 10^18 - 1, inclusive.
-
K will be between 1 and 126, inclusive.
Examples
0)
 
   
10
1
Returns: 4
Here you can compose numbers 10, 19, 16 and 70:
      _                     _
  |  | |     ----->     |  | |
 _|  |_|               _|  |_|
      _                     _
  |  | |     ----->     |  |_|
 _|  |_|               _|   _|
      _                     _
  |  | |     ----->     |  |_
 _|  |_|               _|  |_|
      _                _    _
  |  | |     ----->     |  | |
 _|  |_|                |  |_|
1)
 
   
23
1
Returns: 4
This time it's possible to compose 22, 23, 25 and 33.
2)
 
   
66
2
Returns: 15
Here you can move up to 2 matches, so quite a lot of numbers can be composed. Note that you are allowed to move a match from one digit to another one, so, for example, it's possible to compose 38. However, you can't discard a match or add a new match, so, for example, you can't compose 55 or 88.
3)
 
   
888888888
100
Returns: 1
You are allowed to move a lot of matches, but still it's only possible to compose 888888888.
4)
 
   
444444444444444444
2
Returns: 1
Given that at most 2 matches can be moved, only the initial number can be composed.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Let us define an infinite table of integers as follows:   Each cell is uniquely identified by the value it contains. Let us define S(X) as the sum of all the values in the rectangle with cell 1 as its upper-left corner and cell X as its lower-right corner. For example, S(12) is the sum of all the values in the green rectangle shown above. You are given a long long N. First, find the rectangle with cell 1 as its upper-left corner and cell N as its lower-right corner. Then, calculate the sum of S(X) for all values X inside this rectangle. Return this sum modulo 1,000,000,007. For example, if N is 8, you would first find the 3 x 2 rectangle with 1 in its upper-left corner and 8 in its lower-right corner. You would then calculate S(X) for each value X in this rectangle: S(1) = 1, S(2) = 3, S(9) = 12, S(4) = 5, S(3) = 10, and S(8) = 27. You would them sum these values to get 1 + 3 + 12 + 5 + 10 + 27 = 58.
Definition
   
Class:
MegaSum
Method:
calculate
Parameters:
long long
Returns:
int
Method signature:
int calculate(long long N)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 10^10, inclusive.
Examples
0)
 
   
8
Returns: 58
This is the example from the problem statement.
1)
 
   
12
Returns: 282
 
2)
 
   
11
Returns: 128
 
3)
 
   
6
Returns: 50
 
4)
 
   
34539
Returns: 437909839
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.