程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1757

HDU 1757

編輯:C++入門知識

[a9,a8,a7,…,a0]*
|f(0) 1 0 0,0,0,0,0,0,0|
|f(1) 0 1 0,0,0,0,0,0,0|
|f(2) 0 0 1,0,0,0,0,0,0|
|f(3) 0 0 0,1,0,0,0,0,0|
|f(4) 0 0 0,0,1,0,0,0,0|
|f(5) 0 0 0,0,0,1,0,0,0|
|f(6) 0 0 0,0,0,0,1,0,0|
|f(7) 0 0 0,0,0,0,0,1,0|
|f(8) 0 0 0,0,0,0,0,0,1|
|f(9) 0 0 0,0,0,0,0,0,0|
=[a10,a9,…,a1]
[cpp] 
#include <iostream> 
using namespace std; 
 
int f[10]={0,1,2,3,4,5,6,7,8,9}; 
int a[10]; 
int m; 
 
struct N 

    int ans[10][10]; 
}; 
 
N Get_ans(N a,N b) 

    N temp; 
    int i,j,k; 
    for (i=0;i<10;i++) 
    { 
        for (j=0;j<10;j++) 
        { 
            temp.ans[i][j]=0;//不要忘記 
            for (k=0;k<10;k++) 
            { 
                temp.ans[i][j]+=(a.ans[i][k]*b.ans[k][j])%m; 
                temp.ans[i][j]%=m; 
            } 
        } 
    } 
    return temp; 

 
N run(N node,int n) 

    if(n==1) return node; 
    N rtemp=run(node,n/2); 
    if(n%2) return Get_ans(node,Get_ans(rtemp,rtemp)); 
    else return Get_ans(rtemp,rtemp); 

 
int main() 

    N node; 
    int i,n; 
    memset(node.ans,0,sizeof(node.ans)); 
    for (i=0;i<9;i++) 
    { 
        node.ans[i][i+1]=1; 
    } 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        for(i=0;i<10;i++) 
        { 
            scanf("%d",&node.ans[i][0]);//構造矩陣 
        } 
        if(n<10)//小於10的情況 
        { 
            printf("%d\n",n%m); 
            continue; 
        } 
        N now=run(node,n-9);//node的n-9次 
        int ians=0;//最終結果 
        for (i=9;i>0;i--)//計算結果 
        { 
            ians+=i*now.ans[9-i][0]; 
            ians%=m; 
        } 
        printf("%d\n",ians); 
    } 
    return 0; 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved