SHARE
TWEET

Untitled

a guest Dec 6th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int mul(int a, int b, int m) {
  6.     if (a == 0 || b == 0) {
  7.         return 0;
  8.     }
  9.     if (b == 1)
  10.         return a;
  11.     if (b % 2 == 0) {
  12.         int t = mul(a, b / 2, m);
  13.         return (2 * t) % m;
  14.     }
  15.     return (mul(a, b - 1, m) + a) % m;
  16. }
  17.  
  18. long long **dot(long long ** const A, long long ** const B, int n, int PP) {
  19.     long long **res = malloc(sizeof(long long*) * n);
  20.     for (int i = 0; i < n; ++i) {
  21.         res[i] = malloc(sizeof(long long) * n);
  22.     }
  23.     for (int i = 0; i < n; ++i) {
  24.         for (int j = 0; j < n; ++j) {
  25.             long long sum = 0;
  26.             for (int k = 0; k < n; ++k) {
  27.                 sum += A[i][k] * B[k][j];
  28.                 sum %= PP;
  29.             }
  30.             res[i][j] = sum % PP;
  31.         }
  32.     }
  33.     return res;
  34. }
  35.  
  36. long long **binpow (long long **arr, int n, int k, long long **I, int PP) {
  37.     long long **arr1 = malloc(k * sizeof(long long*));
  38.     for (int i = 0; i < k; ++i) {
  39.         arr1[i] = malloc(sizeof(long long) * k);
  40.         memcpy(arr1[i], arr[i], k * sizeof(long long));
  41.     }
  42.     if (n == 1) {
  43.         return arr;
  44.     }
  45.     if (n == 0)
  46.         return I;
  47.     if (n % 2 == 1)
  48.         return dot(binpow(arr1, n-1, k, I, PP), arr1, k, PP);
  49.     else {
  50.         long long **b = binpow(arr1, n/2, k, I, PP);
  51.         return dot(b, b, k, PP);
  52.     }
  53. }
  54.  
  55. void PowArray (int **res, int **arr, int N, int pow, int PP)
  56. {   int i, j, k, p = 1;
  57.     int **temp = malloc(N * sizeof(int*));
  58.     for (int i = 0; i < N; i++)
  59.     {
  60.         temp[i] = malloc(sizeof(int) * N);
  61.         memset(temp[i], 0, N * sizeof(int));
  62.     }
  63.  
  64.  
  65.     for (i = 0; i<N; i++)
  66.         for (j = 0; j<N; j++)
  67.             res[i][j] = arr[i][j];
  68.  
  69.     while (++p <= pow)
  70.     {   for (i = 0; i<N; i++)
  71.             for (j = 0; j<N; j++)
  72.                 for (k = 0; k<N; k++) {
  73.                      temp[i][j] += res[i][k] * arr[k][j];
  74. //                    temp[i][j] += mul(res[i][k], arr[k][j], PP);
  75.                     temp[i][j] %= PP;
  76.                 }
  77.         for (i = 0; i<N; i++)
  78.             for (j = 0; j<N; j++)
  79.             {   res[i][j] = temp[i][j];
  80.                 temp[i][j] = 0;
  81.             }
  82.     }
  83.  
  84.     //free memory
  85.     for (int i = 0; i < N; i++)
  86.     {
  87.         free(temp[i]);
  88.     }
  89.     free(temp);
  90.  
  91. }
  92.  
  93. int main(void)
  94. {
  95.     int k, n, p;
  96.     scanf("%d %d %d", &k, &n, &p);
  97.     long long *koefs = malloc(k * sizeof(long long));
  98.     long long *firsts = malloc(k * sizeof(long long));
  99.  
  100.     for (int i = 0; i < k; i++)
  101.     {
  102.         scanf("%lld", &firsts[i]);
  103.     }
  104.     for (int i = 0; i < k; i++)
  105.     {
  106.         scanf("%lld", &koefs[i]);
  107.     }
  108.  
  109.     long long **arr = malloc(k * sizeof(long long*));
  110.     long long **res = malloc(k * sizeof(long long*));
  111.     long long **I = malloc(k * sizeof(long long*));
  112.     for (int i = 0; i < k; i++)
  113.     {
  114.         arr[i] = malloc(sizeof(long long) * k);
  115.         res[i] = malloc(sizeof(long long) * k);
  116.         I[i] = malloc(sizeof(long long) * k);
  117.     }
  118.     memcpy(arr[0], koefs, k * sizeof(long long));
  119.     memcpy(res[0], koefs, k * sizeof(long long));
  120.     memset(I[0], 0, k * sizeof(long long));
  121.     for (int i = 1; i < k; i++)
  122.     {
  123.         memset(arr[i], 0, k * sizeof(long long));
  124.         memset(res[i], 0, k * sizeof(long long));
  125.         memset(I[i], 0, k * sizeof(long long));
  126.  
  127.         for (int j = 0; j < k; j++)
  128.         {
  129.             if (j == i - 1) {
  130.                 arr[i][j] = 1;
  131.                 res[i][j] = 1;
  132.             }
  133.         }
  134.  
  135.     }
  136.     for (int i = 0; i < k; ++i) {
  137.         I[i][i] = 1;
  138.     }
  139.     if (n == 1) {
  140.         ;
  141.     } else {
  142.         arr = binpow(res, n - 1, k, I, p); // arr, степень, размерность, единичная матрица, модуль
  143.     }
  144.     long long int ans = 0;
  145.     for (int i = 0; i < k; ++i) {
  146.         ans += arr[k - 1][i] * firsts[k - i - 1];
  147.     }
  148.     printf("%lld\n", ans % p);
  149.     return 0;
  150. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top