233 Matrix(矩阵快速幂+思维)-白红宇

233 Matrix(矩阵快速幂+思维)

阅读量：4360 次

发布时间：2019-06-07

本文共 1965 字，大约阅读时间需要 6 分钟。

In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got ai,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,m in the 233 matrix?

Input

There are multiple test cases. Please process till EOF.

For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).

Output

For each case, output a n,m mod 10000007.

Sample Input

1 112 20 03 723 47 16

Sample Output

234279972937

这个题的难点在于如何去构造矩阵，我们一般的构造矩阵是一维递推式，这个我们也可以通过改变一下就我们让第一行为23，最后一行为3，然后根据递推关系判断

如图：

代码:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              const long long mod=10000007;const int maxn=1e5+5;typedef long long ll;using namespace std;int n,m;struct mat{ ll a[15][15];};mat Mul(mat a,mat b){ mat ans; memset(ans.a,0,sizeof(ans.a)); for(int t=0;t<=n+1;t++) { for(int j=0;j<=n+1;j++) { for(int k=0;k<=n+1;k++) { ans.a[t][j]=(ans.a[t][j]+a.a[t][k]*b.a[k][j])%mod; } } } return ans;}mat anss;ll quickPow(int k){ mat res; memset(res.a,0,sizeof(res.a)); for(int t=0;t<=n;t++) { res.a[t][0]=10; } for(int t=0;t<=n;t++) { for(int j=1;j<=t;j++) { res.a[t][j]=1; } res.a[t][n+1]=1; } for(int t=0;t<=n;t++) { res.a[n+1][t]=0; } res.a[n+1][n+1]=1; while(k) { if(k&1) { anss=Mul(res,anss); } res=Mul(res,res); k>>=1; } return anss.a[n][0]%mod;}int main(){ while(cin>>n>>m) { memset(anss.a,0,sizeof(anss.a)); anss.a[0][0]=23; for(int t=1;t<=n;t++) { scanf("%lld",&anss.a[t][0]); } anss.a[n+1][0]=3; cout<
              
               <

转载于:https://www.cnblogs.com/Staceyacm/p/10781747.html

你可能感兴趣的文章