??

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:??1588?3117?2276?2256?2604?

下面我們研究一下這道題如何運用矩陣。

???? 假設我們已有一個1*10的矩陣f0 f1 f2...f9 只要將其乘以一下矩陣，就可以推導至矩陣f1 f2 f3 ...f10：
??????????????? ??? 0 0 0 0 0 0 0 0 0 a(9)
?????????????????????????? 1 0 0 0 0 0 0 0 0 a(8)?
?????????????????????????? 0 1 0 0 0 0 0 0 0 a(7)?
?????????????????????????? 0 0 1 0 0 0 0 0 0 a(6)?
?????????????????????????? 0 0 0 1 0 0 0 0 0 a(5)?
?????????????????????????? 0 0 0 0 1 0 0 0 0 a(4)
?????????????????????????? 0 0 0 0 0 1 0 0 0 a(3)
?????????????????????????? 0 0 0 0 0 0 1 0 0 a(2)
?????????????????????????? 0 0 0 0 0 0 0 1 0 a(1)?
?????????????????????????? 0 0 0 0 0 0 0 0 1 a(0)??
???? 設這個矩陣為D。

???? f1,f2,f3...f10再乘以這個矩陣就可以推導至f2,f3,f4...f11。以此類推，遞推的過程就變成了不斷乘以這個矩陣的過程。這樣，如果我們要得到fk，我們就得將初始矩陣（f0,f1,f2...f10）乘以D^(k-9)，從而得出目標矩陣（目標矩陣的最后一項即為所求）。而D^(k-9)我們可以用10^3*log(k-9)的時間計算出來，此題圓滿解決。

//看懂這個題解之后就可以知道以后再給出這樣的就該怎么地推求出矩陣表達式

#include <iostream> #include <string.h> #include <cstdio> using namespace std; struct node {long long martix[15][15]; }a,e; int k,m; void init() {memset(a.martix,0,sizeof(a.martix));memset(e.martix,0,sizeof(e.martix));for(int i=0;i<10;++i)e.martix[i][i]=1;for(int i=9;i>=0;--i){cin>>a.martix[i][9];if(i>=1)a.martix[i][i-1]=1;} } node POW(node a,node b) {node ans;for(int i=0;i<10;++i)for(int j=0;j<10;++j){ans.martix[i][j]=0;for(int k=0;k<10;++k){if(a.martix[i][k]&&b.martix[k][j]){ans.martix[i][j]+=(a.martix[i][k]%m*b.martix[k][j]%m)%m;}}}return ans; } void martix_pow(int x) {while(x){if(x&1)e=POW(e,a);a=POW(a,a);x>>=1;} } int main() {while(cin>>k>>m){init();martix_pow(k-9);//long long sum=0;for(int i=0;i<10;++i){sum+=e.martix[i][9]*i%m;}cout<<sum%m<<endl;//注意最后還要%一次，}return 0; }

總結

以上是生活随笔為你收集整理的hdu A Simple Math Problem的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。