If I enter for example 150000 I get overflow , (y-1)x^5 passes limitation of any type. Do I need to create new type to keep ((10^8)^5)size value ? Or anything else I have to do with values, expression? I solved it with that g-function. int g(int x, int y, long long m=9973){ long long lx=x, ly=y, lx2=(lx*lx)%m, lx3=(lx*lx2)%m, lx5=(lx2*lx3)%m; return ( ((ly-1)*lx5)%m + lx3 - (lx*ly)%m + (3*lx)%m + (7*ly)%m) % m; } It may take around ten minutes if you precalc in Python. It takes just few moments to precalc in C++. Maybe special Python libraries for calculations would be OK. There *is* a period of 9973, but not for the given function. Let's denote 9973 as M. ////////////////////////////////////////////////////////////////////////// //In short//////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// 1. g(n) is linear by f(n - 1), and g(x, y) = g(x mod M, y), which means we can find such A and B (in O(M)) that f(x + M) = (A * f(x) + B) mod M. 2. Having found such A and B, it's easy to show that for p > 0, f(p * M) = B * (A^(p-1) + A^(p-2) + .. + A^2 + A + 1) mod M. I'm not sure if the last sum can be calculated in O(1), but it surely can be found in O(M). 3. So, we calc A and B, read N, find f(N - N % M) and then iterate till N in O(M), resulting with overall O(M). ////////////////////////////////////////////////////////////////////////// //In detail/////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// ////// //1.// ////// Let's assume we know f(i) and wish to find f(i+1). Easy to see, g(x, y) = g(x mod M, y). This is why, f(i + 1) = g(i + 1, f(i)) = g((i + 1) mod M, f(i)). Let's denote (i + 1) mod M as j. f(i + 1) = g(j, f(i)) = ((f(i) - 1) * j^5 + j^3 – j * f(i) + 3 * j + 7 * f(i)) mod M f(i + 1) = f(i) * (j^5 - j + 7) + (-j^5 + j^3 + 3 * j) mod M f(i + 1) = f(i) * ((j^5 - j + 7) mod M) + (-j^5 + j^3 + 3 * j) mod M Remembering that j = (i + 1) mod M, let us denote U(i) = (j^5 - j + 7) mod M, V(i) = (-j^5 + j^3 + 3 * j) mod M. As a result: f(i + 1) = U(i) * f(i) + V(i) Note that for any i, we calculate U(i) and V(i) in O(1) time. Also note that U(i) = U(i mod M) and V(i) = V(i mod M): f(i + 1) = U(i mod M) * f(i) + V(i mod M) Let's consider some certain x, and let's denote f(x) as X. f(x+0) == X == 1 * X + 0 == (a0 * X + b0) (mod M) f(x+1) == U(0) * f(x+0) + V(0) == (a1 * X + b1) (mod M) f(x+2) == U(1) * f(x+1) + V(1) == (U(1) * a1) * X + (U(1) * b1 + V(1)) == (a2 * X + b2) (mod M) f(x+3) == U(2) * f(x+2) + V(2) == (U(2) * a2) * X + (U(2) * b2 + V(2)) == (a3 * X + b3) (mod M) f(x+4) == U(3) * f(x+3) + V(3) == (U(3) * a3) * X + (U(3) * b3 + V(3)) == (a4 * X + b4) (mod M) ... f(x+M) == (aM * X + bM)) (mod M) Note that aM and bM do not depend on x - this is the key point! Let's denote aM as A and bM as B. Each iteration above needs O(1) time, so we found A and B in O(M), such that for any x, f(x+M) = (A * f(x) + B) mod M ////// //2.// ////// Consider the following sequence f(0 * M) == 0 (mod M) f(1 * M) == A * f(0 * M) + B == B (mod M) f(2 * M) == A * f(1 * M) + B == A * B + B == B * (A + 1) (mod M) f(3 * M) == A * f(2 * M) + B == A * B * (A + 1) + B == B * (A^2 + A + 1) (mod M) ... f(p * M) == B * (A^(p-1) + A^(p-2) + .. + 1) (mod M) Function A^p mod M is periodic by p with period being divisor of M, so we can easily calculate f(p * M) in O(M) time by summing up first M items of the sequence above. Moreover, for this particular problem p (see below) is very small - less than N/M, so we may calculate this sum explicitly. ////// //3.// ////// The most pleasant part. Given N, we set p to N / M, and calculate f(p * M) with the method desribed above. N - p * M < M, so all we have to do left is explicitly apply the initial formula N - p * M times to find f(N). Edited by author 15.02.2006 18:23 that is the best solution i've ever seen ,thank you Can you explain why did you decide that the coefficients aM and bM don't depend on x? That's right I guess, but it's not evident for me. Why g(x,y) = g(x mod M,y) Correct me if I am mistaken but I think this is because U(i) = U(i mod M) and V(i) = V(i mod M). Can you please tell me is this array correct {0,5392,1890,84,6520,3149,2416,2835,80,8614,742,7696,6823, 9492,7710,9444,510,118,6522,3213,4499,6178,4565,763,1071, 8875,2688,9145,1211,9480,4056,1817,8661,5467,3358,2892, 2205,8691,1963,2386,8401,1047,3691,6824,825,7728,6797,1720 8194,9901,2823,1952,9344,5022,1421,6116,4511,1289,2133, 7494,7298,5012,9638,8753,5968,4029,4804,9556,924,1497,5886 6078,2085,3876,268,2910,8962,2970,1015,3931,1103,4872,4054 346,1119,931,4454,6530,1722,4266,9888,7961,2891,885,4461, 7731,3316,2155,93,2871,9710} q[i]=f(i*10^6),i from 0 to 100 Edited by author 18.12.2006 12:52 Edited by author 18.12.2006 12:53 Your array is like to be correct. But without good calculation of g(x,y) he is useless :) I wrote this function and get the SAME array. But my interval was 500 000 . It's avoid me to get TLE 17 on Java :) easy, you just generate the solutions for 0..100 millions and then you just calculate 1 million values with that algorithme... f(n) depends only from f(n-1), there are 9973 different values, so you can find the period. i don't understand. there may be no period you got AC like this? Can be only 9973 different values of f(n) (0 .. 9972). For each of them we will remember, have we already get it or not. Not more than after 9973 steps we will see repeat. Sequence look like this: a b c ... d (e f g ... h) e ... . Part in brackets is the period. I haven't tried to solve it yet. Well Vlad. It also depends on N as far as I see... Right you are. This function doesn't have period shorter then 3000000 :^) hi, is there any way to solve it without precalculation ?? At least it is uknown to authors of this problem :) f(n+MOD*k) = A*f(n) + B for any 'n'. Just find A and B in O(MOD) and get the result in O(N/MOD + N%MOD) 478704 478705 482574 Thanks. 3446 4179 1766 Thanks U!!! AC!!! Error is found!:) Edited by author 03.04.2007 01:05 47 475 4825 Thanks. Edited by author 07.07.2006 15:07 g(x,y)=((y-1)*x^5+x^3+3*x-x*y+7*y) mod M The result is in 0..M-1 But while counting it I have problems with type. How to make it work with big values (For expample, If x=1000000)? Thanks. Everybody knows... x*x mod m = ((x mod m) * (x mod m))mod m x+x mod m = ((x mod m) + (x mod m))mod m You mean that ((y-1)*x^5) mod M=(((y-1) mod M)*(x mod M)^5) mod M. But x mod M can be 9972 (M=9973) and 9972^5 has 14 digits. It's too much. I know another formula... (x^y) mod M=((((x mod M)*x) mod M)*x) Mod M... y times. But it gets incorrect answer... Can U give me answers for these tests? 1) 9973 2) 19946 3) 29919 4) 8 Thanks. Edited by author 27.06.2006 18:49 you can generate all result with a rate of you generate all values for 1 million, 2 millions and so on. You have only 1000 values. Then you only sweep the interval from previous checkpoint to N. I'm puzzled. I don't understand your way. How to get 2 millions values from 1 million ? You write a stupid program, which calculates values for all n and writes to file values for n = k * 10^6, where k is positive integer. Then you wait few minutes (hours,days...), while your program generates result. You make array of constants, where i-th value is f(n) for n = i * 10^6. When your program gets the value of n it finds k such that k * 10^6 <= n and (k + 1) * 10^6 > n and calculates values f(k*10^6+1),...,f(n). Oh. Thank you very much !!! But I don't think it is a very good way . Do you know the better way ? Oh. Thank you very much !!! Your way is good . I got AC just use 0.062s. But I spend much time on making the answer of 1 , 2 , 3... millions. Edited by author 01.06.2004 20:04 you can generate a value in O(N) time so for 1 billion, the maximum value, the program must run few seconds... mine worked in 10-15... you can generate a value in O(N) time so for 1 billion, the maximum value, the program must run few seconds... mine worked in 10-15... Why must you calculate this for 1 billion? In the problem clearely said: n from 0 to 100,000,000! Thanks to Vlad Veselov! I've got AC! so I was mistaken, it was only 100 mil... so what? big deal... It belongs my friend ! He came from China ! His solution is O(10000) in the worst case ! I haven't understood him yet ! So I will write there to everybody ! If someone understand , please explain for me ! Here the solution : Suppose f(1)=a1*f(0)+b1 (mod 9973), then f(9973*i+1)==a1*f(9973*i)+b1 (mod 9973). So after calculating the (a,b) in f(9973)=a*f(0)+b (mod 9973), then f(9973*(i+1))=a*f(9973)+b (mod 9973) So we can get the algorithm with O(10000) in time.
10000 20000 30000 40000 50000 60000 482574 958764057 2940376458 5629 9205 8753 8937 3321 3760 1766 958764057 and 2940376458 are greater than 10^8... 3x.I got AC now. Please give me answer for N = 100000000 ------------------------------------------- finally, got AC... by the way, right answer for this N is 9710 Edited by author 28.03.2005 20:33 Can anyone give me an answers for these N: 90000 99000 99999 100000 2659 2088 5159 2592 Thank you very much. I got AC. For these values: 46787954 23422479 3214893 16549853 24895423 Or give me a hint about testcase #14. hello my AC says: 5055, 7509, 8753, 7037, 4806 |
|