杭电 1757 A Simple Math Problem （矩阵快速幂）

小咪咪 2022-05-16 13:05 175阅读 0赞

题目链接：[点我][Link 1]

Problem Description  
Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.  
If x >= 10 f(x) = a0 \* f(x-1) + a1 \* f(x-2) + a2 \* f(x-3) + …… + a9 \* f(x-10);  
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

Input  
The problem contains mutiple test cases.Please process to the end of file.  
In each case, there will be two lines.  
In the first line , there are two positive integers k and m. ( k<2\*10^9 , m < 10^5 )  
In the second line , there are ten integers represent a0 ~ a9.

Output  
For each case, output f(k) % m in one line.

Sample Input  
10 9999  
1 1 1 1 1 1 1 1 1 1  
20 500  
1 0 1 0 1 0 1 0 1 0

Sample Output  
45  
104

矩阵快速幂求线性递推式，主要是把转换矩阵求出来，然后直接把矩阵套进快速幂

详细见代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<map>
    #include<vector>
    #include<queue>
    #include<set>
    #include<iomanip>
    #include<cctype>
    using namespace std;
    #define ll long long
    #define edl putchar('\n')
    #define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define FOR(i,a,b) for(int i=a;i<=b;i++)
    #define ROF(i,a,b) for(int i=a;i>=b;i--)
    #define FORLL(i,a,b) for(ll i=a;i<=b;i++)
    #define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
    #define mst(a) memset(a,0,ssizeof(a))
    #define mstn(a,n) memset(a,n,ssizeof(a))
    #define zero(x)(((x)>0?(x):-(x))<eps)
    const int ssize=15;
    int i,j;
    int n,m,f[ssize],a[ssize];
    struct Matrix {
    	ll a[ssize][ssize];
    	Matrix() {
    		memset(a,0,sizeof(a));
    	}
    	void init() {
    		for(int i=0; i<n; i++)
    			for(int j=0; j<n; j++)
    				a[i][j]=(i==j);
    	}
    	Matrix operator + (const Matrix &B)const {
    		Matrix C;
    		for(int i=0; i<n; i++)
    			for(int j=0; j<n; j++)
    				C.a[i][j]=(a[i][j]+B.a[i][j])%m;
    		return C;
    	}
    	Matrix operator * (const Matrix &B)const {
    		Matrix C;
    		for(int i=0; i<n; i++)
    			for(int k=0; k<n; k++)
    				for(int j=0; j<n; j++)
    					C.a[i][j]=(C.a[i][j]%m+1LL*a[i][k]*B.a[k][j]%m+m)%m;
    		return C;
    	}
    	Matrix operator ^ (const ll &t)const {
    		Matrix A=(*this),res;
    		res.init();
    		ll p=t;
    		while(p) {
    			if(p&1)res=res*A;
    			A=A*A;
    			p>>=1;
    		}
    		return res;
    	}
    	
    };
    
    int main() {
        int k,i;
        while(scanf("%d%d",&k,&m)!=EOF)
        {
            n=10;
            for(i=0;i<n;i++)
                scanf("%d",&a[i]);
            f[n]=0;
            for(i=0;i<n;i++)   //求前10项
                f[i]=i;
            for(i=0;i<n;i++)
                f[n]+=a[i]*f[n-1-i];
            if(k<=n)
                printf("%d\n",f[k]);
            else
            {
                Matrix A;
                for(i=1;i<n;i++)    //构造矩阵A
                    A.a[i][i-1]=1;
                for(i=0;i<n;i++)
                    A.a[i][n-1]=a[n-1-i];
                  //A^(k-10)
                
                Matrix res=A^(k-10);
                Matrix origin;
                for(i=0;i<n;i++)   //前10项的矩阵[f(1),f(2),f(3)....f(10)]
                    origin.a[0][i]=f[i+1];
                    //[f(1),f(2),f(3)....f(10)] * A^(n-10)
                Matrix ans;
                ans=origin*res;
                printf("%d\n",ans.a[0][n-1]%m);
            }
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1757