B – A Simple Math Problem

HDU - 1757

矩阵构造入门题

#include<bits/stdc++.h>
using namespace std;

int k,mod;

struct jz{
    int g[20][20];
    void init(){
        memset(g,0,sizeof(g));
    }
    void one(){
        memset(g,0,sizeof(g));
        for(int i = 1; i <= 10; ++ i) g[i][i] = 1;
    }
};
jz operator * (jz a,jz b){
    jz c; c.init();
    for(int i = 1; i <= 10; ++ i) 
    for(int j = 1; j <= 10; ++ j)
    for(int k = 1; k <= 10; ++ k)
    c.g[i][j] += a.g[i][k] * b.g[k][j] % mod, c.g[i][j] %= mod;
    return c;
}
jz ksm(jz x,int y){
    jz z; z.one();
    while(y){
        if(y & 1) z = z * x;
        y >>= 1;
        x = x * x;
    }
    return z;
}

jz a;

int main(){
    while(scanf("%d%d",&k,&mod) != EOF){
        a.init();
        for(int i = 1; i <= 9; ++ i) a.g[i][i + 1] = 1;

        for(int i = 1; i <= 10; ++ i) scanf("%d",&a.g[10][11 - i]);
        if(k < 10) { printf("%d\n",k % mod); continue; }

        k -= 9;
        a = ksm(a,k);

        int ans = 0;
        for(int i = 1; i <= 10; ++ i) 
        ans += (i - 1) * a.g[10][i] % mod, ans %= mod;
        printf("%d\n",ans);
    }
    return 0;
}
/*
1   0100000000                      2
2   0010000000                      3
3   0001000000                      4
4   0000100000                      5
5   0000010000                      6
6   0000001000                      7
7   0000000100                      8
8   0000000010                      9
9   0000000001                      10
10  a10 a9 a8 a7                       11
*/