Advertisement
a53

o_p_t_i_u_n_i

a53
Jun 4th, 2018
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.77 KB | None | 0 0
  1. #include <iostream>
  2. #define DIM 102
  3. #define MOD 666013
  4. using namespace std;
  5.  
  6. char A[DIM][DIM];
  7. int v[DIM], w[DIM];
  8. int D[65][DIM][DIM], P[DIM][DIM], M[DIM][DIM], d[DIM][DIM];
  9. int L, K, X, mic = 1, mare = 2;
  10. long long C;
  11.  
  12. inline int get(int i, int j, int K) {
  13. if (j%K == 0)
  14. return A[i][K] - '0';
  15. else
  16. return A[i][ j%K ] - '0';
  17. }
  18.  
  19. void dinamica(int i, int v[], int tip) {
  20. int aux = K;
  21. if (tip == mic)
  22. K = C;
  23.  
  24. for (int k=0;k<=L+1;k++)
  25. v[k] = 0;
  26. w[0] = w[L+1] = 0;
  27. if (A[i][1] == '0') {
  28. return;
  29. }
  30.  
  31. v[i] = 1;
  32. for (int j=2;j<=K;j++) {
  33. for (i=1;i<=L;i++) {
  34. if (get(i, j, aux) == 1)
  35. w[i] = (v[i-1] + v[i] + v[i+1]) % MOD;
  36. else
  37. w[i] = 0;
  38. }
  39. for (i=1;i<=L;i++)
  40. v[i] = w[i];
  41. }
  42.  
  43. }
  44.  
  45. void produs(int A[DIM][DIM], int B[DIM][DIM], int C[DIM][DIM]) {
  46. for (int i=1;i<=L;i++)
  47. for (int j=1;j<=L;j++) {
  48. C[i][j] = 0;
  49. for (int k=1;k<=L;k++) {
  50. C[i][j] += (A[i][k-1] + A[i][k] + A[i][k+1]) % MOD * 1LL * B[k][j] % MOD;
  51. if (C[i][j] >= MOD)
  52. C[i][j] -= MOD;
  53. }
  54. }
  55. }
  56.  
  57. void copiere(int A[DIM][DIM], int B[DIM][DIM]) {
  58. for (int i=1;i<=L;i++)
  59. for (int j=1; j<=L;j++)
  60. A[i][j] = B[i][j];
  61. }
  62.  
  63. void af(char *msg, int a[DIM][DIM]) {
  64. cout<<msg<<"\n";
  65. for (int i=1;i<=L;i++) {
  66. for (int j=1;j<=L;j++)
  67. cout<<a[i][j]<<" ";
  68. cout<<"\n";
  69. }
  70. cout<<"\n";
  71. }
  72.  
  73. int main () {
  74.  
  75. cin>>L>>K;
  76. for (int i=1; i<=L; i++)
  77. cin>>(A[i]+1);
  78. cin>>X>>C;
  79. if (C <= 3*K) {
  80. dinamica(1, v, mic);
  81. cout<<v[X];
  82. return 0;
  83. }
  84.  
  85. for (int i=1;i<=L;i++) {
  86. dinamica(i, v, mare);
  87. for (int j=1;j<=L;j++)
  88. D[0][i][j] = v[j];
  89. }
  90.  
  91. ///af("D[0]",D[0]);
  92.  
  93. int log = 0;
  94. long long t = K;
  95.  
  96. while (t < C) {
  97. log++;
  98. t *= 2;
  99. }
  100.  
  101. for (int p = 1; p <= log; p++) {
  102. produs(D[p-1], D[p-1], D[p]);
  103. }
  104. ///af("D[1]", D[1]);
  105. long long dim = (C - K - C % K)/K;
  106.  
  107. dinamica(1, v, mare);
  108. for (int j=1;j<=L;j++)
  109. P[1][j] = v[j];
  110.  
  111. int bit = 0;
  112. while (dim != 0) {
  113. if (dim % 2 == 1) {
  114. produs(P, D[bit], M);
  115. copiere(P, M);
  116. }
  117. bit++;
  118. dim /= 2;
  119. }
  120.  
  121. for (int i=1;i<=L;i++)
  122. d[i][0] = P[1][i];
  123.  
  124. for (int j=1;j<=C%K;j++)
  125. for (int i=1;i<=L;i++)
  126. if (A[i][j] == '0')
  127. d[i][j] = 0;
  128. else
  129. d[i][j] = (d[i-1][j-1] + d[i][j-1] + d[i+1][j-1]) % MOD;
  130.  
  131. cout<<d[X][C%K];
  132.  
  133. return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement