Queuing

分析

1. 一般递推式
   

2. 向量递推式
   

代码

#include<bits/stdc++.h>
using namespace std;
#define MXM 4
#define mod(x) ((x)%M)
int L, M, f[5]={0, 2, 4, 6, 9}, A[MXM][MXM]={{1,0,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
struct mat{ 
    int d[MXM][MXM];
    mat operator*(const mat x){
        mat ret;
        int tmp;
        for(int i = 0; i < MXM; i++){
            for(int j = 0; j < MXM; j++){
                tmp = 0;
                for(int k = 0; k < MXM; 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 < MXM; i++)
            for(int j = 0; j < MXM; j++)
                d[i][j] = i == j ? 1 : 0;
    }
    void init(){
        for(int i = 0; i < MXM; i++){
            for(int j = 0; j < MXM; j++){
                this->d[i][j] = A[i][j];
            }
        }
    }
}ma;
mat matrixPow(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", &L, &M) == 2){
        if(L <= MXM){
			printf("%d\n", f[L]%M);
			continue;
		}
        ma.init();
        ma = matrixPow(ma, L-4);
        int ans = 0;
        for(int i = 0; i < MXM; i++)
            ans = mod(ans+ma.d[0][i]*f[MXM-i]);
        printf("%d\n", ans);
    }
	return 0;
}