HDU 1757 A Simple Math Problem (矩陣快速冪)

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1757

在吳神的幫助下才明白如何構造矩陣，還是好弱啊。

此處盜一張圖

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 typedef long long ll;
10 
11 const int N = 10;
12 
13 ll k,m;
14 int a[10];
15 
16 struct matrix
17 {
18     ll mat[N][N];
19 };
20 matrix base;
21 void initial()
22 {
23     memset(base.mat,0,sizeof(base.mat));
24     for(int i=0; i<N; i++)
25         base.mat[0][i]=a[i];
26     for(int i=1; i<N; i++)
27         for(int j=0; j<N; j++)
28             if(i==j+1)
29                 base.mat[i][j]=1;
30 }
31 matrix multi(matrix a,matrix b)
32 {
33     matrix tmp;
34     memset(tmp.mat,0,sizeof(tmp.mat));
35     for(int i=0; i<N; i++)
36         for(int j=0; j<N; j++)
37         {
38             for(int k=0; k<N; k++)
39                 tmp.mat[i][j]=tmp.mat[i][j]+a.mat[i][k]*b.mat[k][j]%m;
40             tmp.mat[i][j]%=m;
41         }
42     return tmp;
43 }
44 
45 ll cal(ll n)
46 {
47     matrix ans;
48     memset(ans.mat,0,sizeof(ans.mat));
49     for(int i=0; i<N; i++)
50         for(int j=0; j<N; j++)
51             if(i==j)
52                 ans.mat[i][j]=1;
53     while(n)
54     {
55         if(n&1)
56             ans=multi(base,ans);
57         base=multi(base,base);
58         n>>=1;
59     }
60 
61     ll sum=0;
62     for(int i=0; i<N; i++)
63         sum+=ans.mat[0][i]*(N-i-1)%m;
64     return sum%m;
65 }
66 int main()
67 {
68     while(~scanf("%lld%lld",&k,&m))
69     {
70         for(int i=0; i<N; i++)
71             scanf("%d",&a[i]);
72         if(k<10)
73             printf("%lld\n",k%m);
74         else
75         {
76             initial();
77             printf("%lld\n",cal(k-9));
78         }
79     }
80     return 0;
81 }

轉載于:https://www.cnblogs.com/ExcuseMe/p/5557624.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257057.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257057.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257057.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！