Ural1309.dpr 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  1. {
  2. http://acm.timus.ru/forum/thread.aspx?space=1&num=1309&id=12571
  3. There *is* a period of 9973, but not for the given function.
  4. Let's denote 9973 as M.
  5. //////////////////////////////////////////////////////////////////////////
  6. //In short////////////////////////////////////////////////////////////////
  7. //////////////////////////////////////////////////////////////////////////
  8. 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.
  9. 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.
  10. I'm not sure if the last sum can be calculated in O(1), but it surely can be found in O(M).
  11. 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).
  12. //////////////////////////////////////////////////////////////////////////
  13. //In detail///////////////////////////////////////////////////////////////
  14. //////////////////////////////////////////////////////////////////////////
  15. //////
  16. //1.//
  17. //////
  18. Let's assume we know f(i) and wish to find f(i+1).
  19. Easy to see, g(x, y) = g(x mod M, y). This is why,
  20. f(i + 1) = g(i + 1, f(i)) = g((i + 1) mod M, f(i)).
  21. Let's denote (i + 1) mod M as j.
  22. f(i + 1) = g(j, f(i)) = ((f(i) - 1) * j^5 + j^3 ¨C j * f(i) + 3 * j + 7 * f(i)) mod M
  23. f(i + 1) = f(i) * (j^5 - j + 7) + (-j^5 + j^3 + 3 * j) mod M
  24. f(i + 1) = f(i) * ((j^5 - j + 7) mod M) + (-j^5 + j^3 + 3 * j) mod M
  25. Remembering that j = (i + 1) mod M, let us denote
  26. U(i) = (j^5 - j + 7) mod M,
  27. V(i) = (-j^5 + j^3 + 3 * j) mod M.
  28. As a result:
  29. f(i + 1) = U(i) * f(i) + V(i)
  30. Note that for any i, we calculate U(i) and V(i) in O(1) time.
  31. Also note that U(i) = U(i mod M) and V(i) = V(i mod M):
  32. f(i + 1) = U(i mod M) * f(i) + V(i mod M)
  33. Let's consider some certain x, and let's denote f(x) as X.
  34. f(x+0) == X == 1 * X + 0 == (a0 * X + b0) (mod M)
  35. f(x+1) == U(0) * f(x+0) + V(0) == (a1 * X + b1) (mod M)
  36. f(x+2) == U(1) * f(x+1) + V(1) == (U(1) * a1) * X + (U(1) * b1 + V(1)) == (a2 * X + b2) (mod M)
  37. f(x+3) == U(2) * f(x+2) + V(2) == (U(2) * a2) * X + (U(2) * b2 + V(2)) == (a3 * X + b3) (mod M)
  38. f(x+4) == U(3) * f(x+3) + V(3) == (U(3) * a3) * X + (U(3) * b3 + V(3)) == (a4 * X + b4) (mod M)
  39. ...
  40. f(x+M) == (aM * X + bM)) (mod M)
  41. Note that aM and bM do not depend on x - this is the key point!
  42. 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,
  43. f(x+M) = (A * f(x) + B) mod M
  44. //////
  45. //2.//
  46. //////
  47. Consider the following sequence
  48. f(0 * M) == 0 (mod M)
  49. f(1 * M) == A * f(0 * M) + B == B (mod M)
  50. f(2 * M) == A * f(1 * M) + B == A * B + B == B * (A + 1) (mod M)
  51. f(3 * M) == A * f(2 * M) + B == A * B * (A + 1) + B == B * (A^2 + A + 1) (mod M)
  52. ...
  53. f(p * M) == B * (A^(p-1) + A^(p-2) + .. + 1) (mod M)
  54. 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.
  55. Moreover, for this particular problem p (see below) is very small - less than N/M, so we may calculate this sum explicitly.
  56. //////
  57. //3.//
  58. //////
  59. 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).
  60. }
  61. {
  62. 1876604 07:08:50 19 Nov 2007 ScaleRhyme 1309 Pascal Accepted 0.015 291 KB
  63. }
  64. {$IFDEF ONLINE_JUDGE}
  65. {$I-,R-,D-,Q-,S-}
  66. {$MODE DELPHI}
  67. {$ENDIF}
  68. Program ScaleRhyme_Ural1309;
  69. Const
  70. Inpath = 'ural.in' ;
  71. Outpath = 'ural.out' ;
  72. ModNum = 9973 ;
  73. Type
  74. TIndex = Longint ;
  75. Var
  76. N,Ans:TIndex;
  77. U,V:Array [1..ModNum] Of TIndex;
  78. A,B:Array [0..ModNum] Of TIndex;
  79. Procedure Init;
  80. Begin
  81. ReadLn(N);
  82. End;
  83. Procedure Main;
  84. Var
  85. I:TIndex;
  86. Begin
  87. Init;
  88. For I := 1 To ModNum Do
  89. Begin
  90. U[I] := (I * I Mod ModNum * I Mod ModNum * I Mod ModNum * I Mod ModNum - I + 7 + ModNum) Mod ModNum ;
  91. V[I] := (I * I Mod ModNum * I Mod ModNum - I * I Mod ModNum * I Mod ModNum * I Mod ModNum * I Mod ModNum + 3 * I Mod ModNum + ModNum) Mod ModNum ;
  92. End;
  93. A[0] := 1 ;
  94. B[0] := 0 ;
  95. For I := 1 To ModNum Do
  96. Begin
  97. A[I] := U[I] * A[I - 1] Mod ModNum ;
  98. B[I] := (U[I] * B[I - 1] Mod ModNum + V[I]) Mod ModNum ;
  99. End;
  100. Ans := 0 ;
  101. For I := 1 To N Div ModNum Do
  102. Ans := (Ans * A[ModNum] + B[ModNum]) Mod ModNum ;
  103. N := N Mod ModNum ;
  104. Ans := (Ans * A[N] + B[N]) Mod ModNum ;
  105. WriteLn(Ans);
  106. End;
  107. Begin
  108. {$IFNDEF ONLINE_JUDGE}
  109. Assign(Input,Inpath);
  110. Reset(Input);
  111. Assign(Output,Outpath);
  112. Rewrite(Output);
  113. {$ENDIF}
  114. Main;
  115. {$IFNDEF ONLINE_JUDGE}
  116. Close(Input);
  117. Close(Output);
  118. {$ENDIF}
  119. End.