Advertisement
a53

o_p_t_i_u_n_i

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