YVNUM Editorial

cook101
editorial
yvnum

#1

PROBLEM LINK:

Practice
Contest

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution


#2

Thanks, very simple and good editorial.


#3

A Python implementation.


#4

Why did you do cur+=MOD ?


#5

Thanks, for this easy explanation . i am constantly getting TLE for this but now i can solve this


#6

i just want to know that is the constraint that N<=10^5 for integer or string of length 10^5


#7

The link to my solution:


#8

Can anybody help? Simple solution but doesn’t work: https://ideone.com/nEqSN1


#9

I was getting TLE as i was doing in O(L*L),now i can do it,good editorial.


#10

It could be rewritten M = N * 10 - a_0 * (10^L - 1). So we only need to calculate 10^L.

And we can do it while calculating N.