SumProduct
SRM 720 · 2017-07-25 · by lg5293
Problem Statement
You are given an array amount with exactly 10 elements, where the i-th element denotes the number of copies of the digit i you have.
You would like to construct construct two nonnegative integers A and B. The base-10 representation of A must have exactly blank1 digits. The base-10 representation of B must have exactly blank2 digits. It is allowed for A and B to contain leading zeros. In addition, the total number of appearances of digit i in the numbers A and B must be at most amount[i]. It's guaranteed that the sum of amount is at least blank1 + blank2.
For every distinct ordered pair (A,B) which you can construct, compute the product A * B. Return the sum of all these products, modulo 10^9+7.
Constraints
- amount will have exactly 10 elements.
- Each element of amount will be between 0 and 100.
- blank1, blank2 will be between 1 and 100, inclusive.
- The sum of elements in amount will be at least blank1 + blank2.
{0,2,1,1,0,0,0,0,0,0}
2
2
Returns: 4114
The different choices for (A,B) are (11, 23), (11, 32), (12, 13), (12, 31), (13, 12), (13, 21), (21, 13), (21, 31), (31, 12), (31, 21), (23, 11), (32, 11). The sum of all products A * B is 4114.
{1,6,0,0,0,0,0,0,0,0}
1
2
Returns: 22
Remember that the numbers are allowed to have leading zeros.
{1,2,3,4,5,6,7,8,9,10}
15
3
Returns: 340242570
Don't forget about the mod.
{3,14,15,92,65,35,89,79,32,38}
46
26
Returns: 417461139
{100,100,100,100,100,100,100,100,100,100}
100
100
Returns: 372980218
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SumProduct with a public method int findSum(vector<int> amount, int blank1, int blank2) · 108 test cases · 2 s / 256 MB per case