PROBLEM LINK:
Setter- Varad Kulkarni
Tester- Misha Chorniy
Editorialist- Abhishek Pandey
DIFFICULTY:
SIMPLE
PRE-REQUISITES:
PROBLEM:
Given a value of N, number of digits in a number D_1D_2D_3...D_N, and W which is given by W=\sum_{i=2}^N (D_i - D_{i-1})\,, we have to find number of N digit numbers which have weight W modulo {10}^{9}+7.
QUICK EXPLANATION:
We can reduce the expression to W=D_n-D_1 where D_n is the rightmost digit, and D_1 is the leftmost digit. We see that we can find valid numbers only for -9\le W \le 8, for all other values of W the answer is 0. If -9\le W \le 8, we brute force the pair of digits (D_1,D_N) such that D_N-D_1=W. Let this be denoted by cnt. Clearly, answer is cnt*{10}^{N-2}\% ({10}^{9}+7)
EXPLANATION:
" Oh…This question…This question has that "\sum" symbol…It must be…It must be very difficult."
If you left the question because of above belief, then dont read this editorial. You’re gonna regret that decision of yours 
For this question, since Editorialist’s , Tester’s, and Setter’s, all three have use a similar approach, so the approach will be described in a bit more detail. After discussing the intuition and approach, we will see tester’s idea to further reduce time complexity in the bonus section :).
Editorialist’s/Tester’s/Setter’s Solution-
The very first thing we need to look at is the constraints. We have number of test cases, T as 1\le T \le {10}^{5} and 2 \le N \le {10}^{18} , which clearly hints that we need to answer to answer each test case in O(logN) or O(1) complexity.
With that in mind, we should first try to simplify the summation. Carefully look at the summation W=\sum_{i=2}^N (D_i - D_{i-1})\, and try to expand it. On expanding it, we get-
W=\sum_{i=2}^N (D_i - D_{i-1})\,
=(D_2-D_1)+(D_3-D_2)+(D_4-D_3)......(D_N-D_{N-1})
We see that we can cancel some terms above. Upon cancelling, we are left with-
W=D_N-D_1 where 0 \le D_i\le9.
This means W is nothing but difference of first and last digit of the number. This restricts valid values of W to -9\le W \le 8. No answer exists for any value outside this range.
The first conclusion, hence, is that answer for W outside the range [-9,8] is 0 as no such N digit number exists.
Now, how to find W for -9\le W \le 8 ?
We notice that for answer to exist, we need to put adjust only D_n and D_1, while any other digit D_i in between can take any value from [0,9]. Lets focus on valid pairs of (D_1,D_N) right now.
What we can do is, we can brute-force all possible pairs of (D_1,D_N), and count the number of pairs satisfying D_N-D_1=W. Let this be denoted by cnt. Or, you can simply find the number of valid pairs by this formula-
if(w>=0)//Proof -By simple counting of pairs
cnt=9-abs(w);
else
cnt=10-abs(w);
Please note that D_1 (leftmost digit) cannot be 0 as leading 0's are not allowed.
Now we have the number of valid pairs of (D_1,D_N) in cnt. What about the rest of the digits? We see that the answer is independent of all other digits. Thus, all the remaining N-2 digits can take any value between [0,9].
So, we have cnt choices for D_1,D_N and {10}^{N-2} choices for rest of the N-2 digits. Thus, the answer will be cnt*{10}^{N-2}\% ({10}^{9}+7). We will calculate {10}^{N-2}\% ({10}^{9}+7) using fast exponentiation. (Link to algo given under pre-requisites).
Time Complexity= O(T*LogN)
SOLUTION:
Setter
Tester - O(Log(MOD) solution by Misha. 
Tester - O(1) solution by Misha 
Editorialist’s
CHEF VIJJU’S CORNER:
**1.**During contest, this question was flooded with comments- with everyone speaking the same thing - “Are constraints wrong?” or “How can W be >10? Why do
constraints have W upto 300?” . &etc. While almost EVERYONE derived that formula that W=D_N-D_1, they all got stuck at this trivial stuff that why is W upto 300 in problem statement.
Whats worse, they started feeling that since |W|\le 300 in the question, perhaps their derivation and understanding of the question is wrong. I have nothing to say here, except that
if you yourself arent confident at your solution, dont expect anyone else to. Have confidence in what you do, and at the same time learn to accept when you go wrong. Balance these two things, and
thats the secret of life :).
2. I have to mention Misha’s immense variety of solution. If you see tester’s code (the O(Log(MOD)) one), he has used something different. He used bpow(10, (n - 2) % (MOD - 1)), while setter and me have simply used count*fastExpo(10,n-2) (fastExpo and bpow, both are same). He framed that solution based on Euler’s Totient Function and Euler’s theorem. Go through the given links, try to derive the expression. Answer is in the tab below to cross check :).
Click to view
We know that {10}^{9}+7 is prime. Let us denote is by MOD. Also, we will denote Euler’s totient function for n as \phi(n).
We know that, if a number p is prime, \phi(p)=p-1.
\implies \phi(MOD)=MOD-1
Now, by Euler’s theorem, we know that {A}^{\phi(p)} \equiv 1 (mod p) provided that A and p are relatively co-prime.
\because {A}^{N}={A}^{Q*\phi(MOD)+R} (where Q is quotient and R is remainder from division of N by \phi(MOD))
= {A}^{Q*\phi(MOD)}*{A}^{R}
=1*{A}^{R}
={A}^{R}
And R is nothing but N\% \phi(MOD)=N\%(MOD-1)
3. Dont open the tab below.
Click to view
Vijju123: Hey Misha!
Misha: Yes?
Vijju123: You did derive a nice O(Log(MOD)) solution, but I think it wont make much of a difference. Its still computationally expensive per test case.
Misha: Hmm…?
Vijju123: I mean, yeaah we can call it O(1) but I wont call it "True O(1)" because its expensive.
Misha: O(1) solution coming in 10 minutes.
Vijju123: …
Now, Misha did not want to stop at O(Log(MOD) solution, so he devised an O(1) solution! Basically, that solution uses pre-processing. What he did is, we know that MOD <{2}^{30}. Hence, the highest value which we deal with can be represented within 30 bits.
He took the binary representation of number , and partitioned it into 3 parts, consisting 10 bits each. (Remember we can represent the numbers within 30 bits).
Now, he uses his POW00[],POW10[],POW20[] arrays to calculate any power of 10 from [0,MOD] in O(1) time. POW00[] is simple, it just stores powers of 10 mod {10}^{9}+7 for powers from [0,1023]. Imagine it like this, we partitioned the 30-bit number into 3 part of 10 bits each. POW00[] deals with lowest 10 bits. Multiplying previous element by 10 is like adding 1 to power of previous element, (which , in terms of binary numbers, is essentially adding 1 to binary representation of the number. ) Recurrence formula-
POW00[i]=10*POW[i-1];
He does the same in POW10[] array. He adds 1 to binary representation of number- but he is careful of one thing. POW00[] dealt with numbers from [0,{2}^{10}-1], where the value of LSB is 1. However, in case of POW10[], the LSB is (in reality) the 11 'th bit of the number. Hence, we multiply it with {10}^{1024} instead of 10.
POW10[i]={10}^{{2}^{10}}*POW10[i-1];
Similarly, in POW20[], the recurrence relation is POW20[i]={10}^{{2}^{20}}*POW20[i-1]. Its basically, he is adding 1 to the LSB of the 10-bit partition. And adding one there, means we must multiply it with 10, raised to power equal to value of that LSB. His generator code is given below for the curious :).
Click to view
His generator code for the array values.
int mul20 = 1, mul10 = 1;
for (int i = 0; i < 1 << 20; ++i) {
mul20 = 10LL * mul20 % MOD;
if (i % (1 << 10) == 0) {
mul10 = 10LL * mul10 % MOD;
}
}
cout << "int PW20[] = {";
for (int i = 0, now = 1; i < 1 << 10; ++i) {
printf("%d%c", now, i == 1023 ? ' ' : ',');
now = 1LL * now * mul20 % MOD;
}
cout << "};\n";
cout << "int PW10[] = {";
for (int i = 0, now = 1; i < 1 << 10; ++i) {
printf("%d%c", now, i == 1023 ? ' ' : ',');
now = 1LL * now * mul10 % MOD;
}
cout << "};\n";
cout << "int PW00[] = {";
for (int i = 0, now = 1; i < 1 << 10; ++i) {
printf("%d%c", now, i == 1023 ? ' ' : ',');
now = 1LL * now * 10 % MOD;
}
cout << "};\n";*/
int t;
4. Some of the good questions on fast exponentiation-
-
Tower 3-coloring - Give Fermat’s Little Theorem a read first and you’re good to go
- BROCLK - While also solvable via Matrix Exponentiation, I solved this problem by nested/dual Fast-Exponentiation.
- Chef and Segments - Fast Exponentiation +Maths.
