uva 10870

https://vjudge.net/problem/UVA-10870

题意：

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f(1),f(2) ... f(d) 以及a1,a2...ad，然后给出一个n和m的值，计算f(n) % m的值

思路：

矩阵快速幂模板题，只是构建矩阵比较困难，其实这题的构建矩阵是比较简单的，这题的模型也是一个相当广泛的模型。

|a1 a2 a3 a4 a5| | f[n] | | f[n+1] |
|1 | | f[n-1] | | f[n] |
| 1 | * | f[n-2] | = | f[n-1] | (空白处为0)
| 1 | | f[n-3] | | f[n-2] |
| 1 | | f[n-4] | | f[n-3] |

就是这样一个关系，可以用手推一下。

f(n) = A^(n-d) * f(d);

之后就直接套模板啦。

最后的f(n)其实是通过得到的结果矩阵的第一行乘以f(d)这个矩阵得到的，只不过乘的时候要关注原矩阵的顺序，别乘反了。

注意在n <= d的时候是直接取余输出的。（矩阵乘法的时候也要一边乘，一边取余）。

代码：

 #include <stdio.h>

 #include <string.h>

 long long d,n,m;

 long long f[];

 struct matrix

 {

     long long a[][];

 };

 matrix mul(matrix x,matrix y)

 {

     matrix c;

     for (int i = ;i < d;i++)

         for (int j = ;j < d;j++)

     {

         c.a[i][j] = ;

         for (int k = ;k < d;k++)

         {

             c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % m) % m;

         }

     }

     return c;

 }

 void solve(matrix t,long long o)

 {

     matrix e;

     memset(e.a,,sizeof(e.a));

     for (int i = ;i < d;i++)

         e.a[i][i] = ;

     while (o)

     {

         if (o & )

         {

             e = mul(e,t);

         }

         o >>= ;

         t = mul(t,t);

     }

     long long res = ;

     for (int i = ;i < d;i++)

         res = (res + e.a[][i] * f[d-i-]) % m;

     printf("%lld\n",res);

 }

 int main()

 {

     while (scanf("%lld%lld%lld",&d,&n,&m) != EOF)

     {

         if (d ==  && n ==  && m == ) break;

         matrix p;

         memset(p.a,,sizeof(p.a));

         for (int i = ;i < d;i++)

             scanf("%lld",&p.a[][i]);

         for (int i =  ;i < d;i++)

             p.a[i][i-] = ;

         for (int i = ;i < d;i++)

             scanf("%lld",&f[i]);

         if (n <= d)

         {

             printf("%lld\n",f[n-] % m);

             continue;

         }

         solve(p,n-d);

     }

     return ;

 }

巴特西

uva 10870

最新文章

热门文章