HDU1757 A Simple Math Problem——————矩阵快速幂

矫情吗；* 2022-05-09 11:12 170阅读 0赞

# A Simple Math Problem #

**Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 6573 Accepted Submission(s): 4033**

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

Author

linle

Source

2007省赛集训队练习赛（6）\_linle专场

Recommend

lcy | We have carefully selected several similar problems for you: 1575 1588 3117 2276 2256

Statistic | Submit | Discuss | Note

--------------------

矩阵快速幂解决  
第一步，构造矩阵：  
 ( a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 ) × ( f x − 1 f x − 2 f x − 3 f x − 4 f x − 5 f x − 6 f x − 7 f x − 8 f x − 9 f x − 10 ) = ( f x f x − 1 f x − 2 f x − 3 f x − 4 f x − 5 f x − 6 f x − 7 f x − 8 f x − 9 ) \\begin\{pmatrix\} a\_0 & a\_1 & a\_2 & a\_3 & a\_4& a\_5 & a\_6& a\_7 & a\_8&a\_9\\\\ 1&0 &0 &0 &0 &0 &0 &0 &0 &0 \\\\ 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &1 &0 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &1 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &1 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &1 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &1 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &0 &1 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &0 &0 &1 &0 \\\\ \\end\{pmatrix\}\\times \\begin\{pmatrix\}f\_\{x-1\}\\\\f\_\{x-2\}\\\\f\_\{x-3\}\\\\f\_\{x-4\}\\\\f\_\{x-5\}\\\\f\_\{x-6\}\\\\f\_\{x-7\}\\\\f\_\{x-8\}\\\\f\_\{x-9\}\\\\f\_\{x-10\}\\end\{pmatrix\} =\\begin\{pmatrix\}f\_\{x\}\\\\ f\_\{x-1\}\\\\f\_\{x-2\}\\\\f\_\{x-3\}\\\\f\_\{x-4\}\\\\f\_\{x-5\}\\\\f\_\{x-6\}\\\\f\_\{x-7\}\\\\f\_\{x-8\}\\\\f\_\{x-9\}\\end\{pmatrix\} ⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛a0100000000a1010000000a2001000000a3000100000a4000010000a5000001000a6000000100a7000000010a8000000001a9000000000⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞×⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛fx−1fx−2fx−3fx−4fx−5fx−6fx−7fx−8fx−9fx−10⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛fxfx−1fx−2fx−3fx−4fx−5fx−6fx−7fx−8fx−9⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞  
然后利用矩阵快速幂求得：  
 ( a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 ) n − 9 × ( f 9 f 8 f 7 f 6 f 5 f 4 f 3 f 2 f 1 f 0 ) = ( f n f n − 1 f n − 2 f n − 3 f n − 4 f n − 5 f n − 6 f n − 7 f n − 8 f n − 9 ) \\begin\{pmatrix\} a\_0 & a\_1 & a\_2 & a\_3 & a\_4& a\_5 & a\_6& a\_7 & a\_8&a\_9\\\\ 1&0 &0 &0 &0 &0 &0 &0 &0 &0 \\\\ 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &1 &0 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &1 &0 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &1 &0 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &1 &0 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &1 &0 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &0 &1 &0 &0 \\\\ 0&0 &0 &0 &0 &0 &0 &0 &1 &0 \\\\ \\end\{pmatrix\}^\{n-9\}\\times \\begin\{pmatrix\}f\_\{9\}\\\\f\_\{8\}\\\\f\_\{7\}\\\\f\_\{6\}\\\\f\_\{5\}\\\\f\_\{4\}\\\\f\_\{3\}\\\\f\_\{2\}\\\\f\_\{1\}\\\\f\_\{0\}\\end\{pmatrix\} =\\begin\{pmatrix\}f\_\{n\}\\\\ f\_\{n-1\}\\\\f\_\{n-2\}\\\\f\_\{n-3\}\\\\f\_\{n-4\}\\\\f\_\{n-5\}\\\\f\_\{n-6\}\\\\f\_\{n-7\}\\\\f\_\{n-8\}\\\\f\_\{n-9\}\\end\{pmatrix\} ⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛a0100000000a1010000000a2001000000a3000100000a4000010000a5000001000a6000000100a7000000010a8000000001a9000000000⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞n−9×⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛f9f8f7f6f5f4f3f2f1f0⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛fnfn−1fn−2fn−3fn−4fn−5fn−6fn−7fn−8fn−9⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞

--------------------

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN =  13;
    
    struct mat{
        ll m[MAXN][MAXN]; };
    
    ll n,MOD;
    ll N,k,b_n=0;
    ll C[MAXN],h[MAXN];
    
    mat mul(mat a,mat b)//矩阵乘法
    {
        
            mat tmp;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                    {
        
                            tmp.m[i][j]=0;
                            for(int k=1;k<=N;k++)
                                    tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
                    }
            return tmp;
    }
    mat pow_mod(mat a,ll n)
    {
        
            mat ans;
            for(int i=1;i<=N;i++)//构造单位矩阵
                    for(int j=1;j<=N;j++)
                            ans.m[i][j]=(i==j);
            while(n)//矩阵快速幂
            {
        
                    if(n&1) ans=mul(ans,a);
                    a=mul(a,a);
                    n>>=1;
            }
            return ans;
    }
    
    void init(mat &res,mat &H)//构造矩阵
    {
        
            for(int i=1;i<=N;i++)
                    res.m[1][i]=C[i];
            res.m[1][N]=b_n;
            for(int i=2;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            res.m[i][j]=(i==j+1);
            res.m[N][N-1] = 0;
            res.m[N][N]   = 1;
            for(int i=1;i<=N;i++)
            {
        
                    H.m[i][1]=h[N-i];
                    for(int j=2;j<=N;j++)
                            H.m[i][j]=0;
            }
            H.m[N][1]=1;
    }
    void slove(ll k,ll n)
    {
        
            mat res,H;
            init(res,H);
            res = pow_mod(res,n-k+1);
            res = mul(res,H);
            ll ans=res.m[1][1];
    
            printf("%lld\n",ans%MOD);
    }
    
    int main()
    {
        
            k=10; N=11;
            for(int i=1;i<=k;i++)   h[i]=i-1;
    
            while(~scanf("%lld %lld",&n,&MOD))//f(n)%MOD;,我更习惯这样写
            {
        
    
                    for(int i=1;i<=k;i++)
                            scanf("%lld",&C[i]);//第一次没有加&，找了好久。。。我好傻
                    if(n<10)
                    {
        
                            printf("%d\n",n);
                            continue;
                    }
                    slove(k,n);
            }
            return 0;
    }