PROBLEM LINK:
Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi
PREREQUISITES:
NONE
PROBLEM:
Given a decimal integer N (with no zeroes at all even as intermediate digits). Consider all left cyclic shifts of N. The left cyclic shift is the operation of removing the leftmost digit from the number and appending it to the end.
Suppose N = 123 then all left cyclic shifts are {123,231,312}. So you start with N and repeat the mentioned operation N-1 times.
Yalalovichik number of N is equal to the concatenation of all these cyclic shifts.
For the previous example:
Y = 123231312.
Given N, you need to compute the value of Y modulo 10^9+7
Length of N may reach 10^5
EXPLANATION:
Let’s assume that length of N is equal to L. We know that:
N = a_0*10^{L-1} + a_1*10^{L-2} + a_2*10^{L-3} + ... + a_{L-1}
Assuming that digits are indexed from 0 to L-1 and from left to right. a_0 represents the leftmost digit. So let’s assume we need to do one shift operation, how to erase the leftmost digit?
N' = N - a_0*10^{L-1}
N' is equal to the value of N after removing the leftmost digit.
Let’s assume that the number resulting from the shift is M so:
M = N' * 10 + a_0
so now the number resulting from the shift is M we need to append it to our final answer. At the beginning the answer ans = N. To append it let’s shift ans to the left by L digits and simply add M.
ans = ans * 10^L + M
This is for the first shifting operation, to solve the problem repeat this operation N-1 times, but don’t forget to continue working on the shifted number.
We only need to calculate 10^L and 10^{L-1}, this can be done in linear time or faster if you prefer.
To maintain the answer modulo 10^9+7 we calculate the powers mentioned above modulo 10^9+7 and we always take our results modulo 10^9+7 after each subtraction or multiplication or addition.
Refer to the implementations for more details.
Total Complexity O(L)