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

分析

f的递推关系

代码

#include
   
    using namespace std;#define mod(x) ((x)%m)int k, m;struct mat{
        int d[10][10];    mat operator*(const mat x){
           mat ret;        int tmp;        for(int i = 0; i < 10; i++){
               for(int j = 0; j < 10; j++){
                   tmp = 0;                for(int k = 0; k < 10; k++){
                       tmp = mod(tmp + d[i][k]* x.d[k][j]);                }                ret.d[i][j] = tmp;            }        }        return ret;    }    void init_unit(){
           for(int i = 0; i < 10; i++)            for(int j = 0; j < 10; j++)                d[i][j] = i == j ? 1 : 0;    }    void init(){
           for(int i = 0; i < 10; i++)            for(int j = 0; j < 10; j++)                d[i][j] = i == j+1 ? 1 : 0;    }    void set(int i, int v){
           d[9-i][9] = v;    }}a;mat fastPow(mat base, int pow){
       mat res;    res.init_unit();    while(pow){
           if(pow & 1) res = res * base;        base = base * base;        pow >>= 1;    }    return res;}int main(){
   	int tmp;    while(scanf("%d%d", &k, &m) == 2){
           if(k < 10){
    // 猜测：本题无此测试数据			printf("%d\n", k%m);			continue;		}        a.init();        for(int i = 0; i < 10; i++)            scanf("%d", &tmp), a.set(i, tmp);                a = fastPow(a, k-9);        int ans = 0;        for(int i = 0; i < 10; i++)            ans = mod(ans+a.d[i][9]*i);        printf("%d\n", ans);    }	return 0;}
   

转载地址：http://dwib.baihongyu.com/