There is a typo: 24 * 1 = 1

Should be: 24 * 1 = 24.

can you explain about the second argument in your change function? Your solution is recursive. I can convert it to non-recursive version if I understand the trick.

The input is n<=3*10^5, m <= 9*10^5, about 10^7. It's just too large for python. My C++ solution cost 375ms and my python solutions are always 10 times slower. So I guess python need about 4 seconds for each test case.

I use segment tree, too. I've got some MLE after some TLE and finally I forgot to use long long.

You shouldn't continue on a[i] == a[j] at line 40.

And you use insertion sort which is O(n^2). I think it will timeout before finishing input.

When the data scale is too large, we will lost some interesting solutions. It's also unfair for some dynamic languages since a loop with 1000000 times may cost about 1 sec. So I think 10^3 or 10^5 is fine.

Actually, it is the correct understanding.

You guys use hash without handling conflict, and still got ACCEPTED! How unfair... I found a nice c++ solution(3100030) in my room that use set<string>, and the worst time complexity is O(n^3 log(n)), still very nice, though.

My first attempt was a Python solution using a Trie, which is O(n^2). It got TLE, saddly. Then I was forced to translate the Python script into C++.

dp[i][j][s] = k, means there are k ways to accomplish event (i, j, s), where event (i, j, s) is : let j of the first i people come in, with total length s.

dp[i, j, s] = dp[i-1, j-1, s — len[i]] * j + dp[i-1, j, s]

f(n) = f(n-1) * (2^m — (n-1) — 1), f(1)=2^m-1. Here 2^m — (n-1) -1 means you have this number of ways to append a number to the valid sequence with length n-1. "-1" since you cannot use 0.

I think few OJs have command line submit tool because they are afraided that the users submit too fast.

In 235B, what do you mean by:

So if they are i, j , ....

Oh, thank you for translating my Python code here. * P.S. It's ray0(4)0123

I got this solution 5 minutes after the contest, saddly. Then I waited hours for the system test to end. Finally I got 1AC.

Let E[i, j] be the excepted score for clicks from i to j(inclusive). Let L[i, j] be the excepted 'o' s starts from left, of clicks from i to j. Let R[i, j] be something like L[i, j]. Then we have:

E[i, j] = E[i, k] + E[k + 1, j] + 2 * R[i, k] * L[k+1, j]

, for any i < k < j.

Think about: If we got x 'o's in clicks [i..k], y 'o's in clicks [k+1..j], then score x^2 is calculated in E[i, k], y^2 in E[k+1, j], and we actually need (x+y)^2 = x^2+y^2+2xy. And since R[i, k] and L[k+1, j] are independent, the 2xy part is calculated as 2 * R[i, k] * L[k+1, j].

Now we take k = j — 1, i = 0, and let e[j] = E[0, j], r[j] = R[0, j]:

e[j] = E[0, j] = E[0, j-1] + E[j, j] + 2 * R[0, j-1] * L[j,j] 
     = e[j-1] + p[j] + 2 * r[j] * p[j]
r[j] = (r[j-1] + 1) * p[j]

You are purple now.

I skipped my class to play in the contest. XD!!!!

The first argument of recfib, namely n, will not affected by m.

2251104 Even shorter(7 lines) with functional style. Accepted.

def recfib(n,m):
    if n == 0: return (0, 1)
    a, b = recfib(n / 2,m)
    return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)
def next_d(D): return D if 1+r/D-(l+D-1)/D>=k else next_d(D-(D-r%D+r/D)/(1+r/D))
m, l, r, k = map(long, raw_input().split())
print recfib(next_d((r-l)/(k-1)), m)[0]

# Trick to remove N from the code: N = 1 + r / D
# D -= (N*D-r + N - 1)/N
#   N*D - r = (D + r - r % D - r) = (D - r % D)
#   N*D - r + N - 1 = D - r % D + r / D

Actually, you don't need so many '%m' in python. For example, it will convert to long for you automatically if a*a+b*b run out of the range of int. And -1 % 5 == 4 in python.

Btw, after I copy your code to my editor, the first thing I do is to remove the import line and replace sys.stdin... by raw_input().split().

Your code cannot pass the tests. You put the '%m' in wrong places. After my modification it passed.

And, spliting the long long return statement in recfib using the V1 if C else V2 expression would make the code faster, since that can supress the useless evaluation.

    return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)

See, it's only 80 chars. You don't even need to break the line.

Nice solution! Can you explain that the meaning of (a, b) in a, b = recfib(n, m)

I guess a is the n(th) fib number. But what's b?