NEUQ —— 1768 一道简单的递推题（矩阵快速幂）

逃离我推掉我的手 2021-09-26 16:10 274阅读 0赞

题目链接：[http://geek.acmclub.cn/problems/1768][http_geek.acmclub.cn_problems_1768]

题目：

## 1768: 一道简单的递推题 ##

题目描述：

存在如下递推式:

F(n+1)=A1\*F(n)+A2\*F(n-1)+...+An\*F(1)

求第K项的值对1000000007取模的结果

输入：

单组测试数据

第一行输入两个整数 n , k (1<=n<=100,n<k<=10000000000)

第二行输入 n 个整数 F(1)   F(2)   ...   F(n)

第三行输入 n 个整数A1   A2   ...   An

输出：

输出一个整数

样例输入

2   3
    1   2
    3   4

样例输出

题目描述：

用矩阵快速幂求解，构造矩阵乘积

f\[n\]    0 0 0                    A\[1\]   A\[2\]   A\[3\]  ···   A\[n\]                   f\[n+1\]   0 0 0

f\[n-1\] 0 0 0         ×        1         0         0           0             ＝      f\[n\]       0 0 0

···                                   0         1         0           0                       ···

f\[1\]    0 0 0                    0         0         1           0                       f\[2\]       0 0 0

矩阵都是n×n的，不明白的可以先看看矩阵快速幂求解斐波那契数列，实际上就是把快速幂的思想用在了矩阵相乘上面，所以矩阵一定是n×n的形式，明白了原理，只需推出矩阵的公式就可以了。

代码：

#include<stdio.h>
    #include<string.h>
    const long long  M = 1000000007;
    long long n,m;
    long long f[110];
    typedef struct e
    {
    	long long a[110][110];
    }e;
    e po_(e q , e w)    //矩阵相乘部分
    {
    	long long i,j,k;
    	e r;
    	memset(r.a,0,sizeof(r.a));
    	for(i = 0;i < n;i++){
    		for(j = 0;j < n;j++){
    			for(k = 0;k < n;k++){
    				r.a[i][j] += ((q.a[i][k]%M) * (w.a[k][j]%M)) % M;
    				r.a[i][j] %= M;
    			}
    		}
    	}
    	return r;
    }
    long long po(e A, long long x)        //快速幂部分
    {
    	e E;
    	long long i;
    	memset(E.a,0,sizeof(E.a));
    	for(i = 0;i < n;i++)	E.a[i][i] = 1;
    	while(x){
    		if(x&1LL)	E = po_(E,A);
    		A = po_(A,A);
    		x >>= 1;
    	}
    	long long sum = 0;
    	for(i = 0;i < n;i++)
    		sum+=((E.a[0][i]%M)*(f[i]%M))%M,sum%=M;
    	return sum;
    }
    int main()
    {
    	long long i,j,k;
    	e A;
    	while(scanf("%lld%lld",&n,&m)!=EOF){
    		memset(A.a,0,sizeof(A.a));
    		for(i = 1;i<n;i++)	A.a[i][i-1] = 1;	
    		for(i = n-1;i >= 0 ;i--)	scanf("%lld",&f[i]);
    		for(i = 0;i < n;i++)	scanf("%lld",&A.a[0][i]);
    		m-=n;
    		long long T = po(A,m);	
    		printf("%lld\n",T);
    	}
    	return 0;
    }

[http_geek.acmclub.cn_problems_1768]: http://geek.acmclub.cn/problems/1768