佳佳的Fibonacci

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=5;
const int N=4;
ll n,m,f2,f1,s1,p1;
ll sn,pn,tn;
struct node{
    ll g[M][M];
}mat,res;
void matrixMutiple(node &x,node &y,node &z){
    //矩阵乘法运算
    memset(z.g,0,sizeof(z.g));
    for(int i = 1; i<=N; i++){
        for(int j=1; j<=N; j++) if(x.g[i][j]){
            for(int k=1; k<=N; k++){
                z.g[i][k]+=x.g[i][j]*y.g[j][k];
                if(z.g[i][k]>=m) z.g[i][k]%=m;
            }
        }
    }
}
void matrixI(node &E){
    //构造单位矩阵
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) E.g[i][j]=(i==j);
    }
}
void matrixMuti(ll k){
    //快速幂运算
    matrixI(res); node tmp=mat, t;
    while(k){
        if(k&1) {//“&1”判断k的奇偶 
            matrixMutiple(res,tmp,t); res=t;
        }
        matrixMutiple(tmp,tmp,t); tmp=t;
        k>>=1;
    }
}
void init(){
    //初始化矩阵
    memset(mat.g,0,sizeof(mat.g));
    mat.g[1][1]=1; mat.g[1][2]=1;
    mat.g[2][1]=1;
    mat.g[3][1]=1; mat.g[3][3]=1;
    mat.g[4][3]=1; mat.g[4][4]=1;
    f1=f2=s1=1; p1=0;
}
int main(){
    ios::sync_with_stdio(false); //加速cin和cout 
    while(cin>>n>>m){
        init();
        ll ans=0;
        matrixMuti(n-1);
        sn=(res.g[3][1]*f2+res.g[3][2]*f1+res.g[3][3]*s1+res.g[3][4]*p1)%m;
        pn=(res.g[4][1]*f2+res.g[4][2]*f1+res.g[4][3]*s1+res.g[4][4]*p1)%m;
        tn=(n*sn-pn+m)%m;
        cout<<tn<<endl;
    }
    return 0;
}

佳佳的Fibonacci：

时间限制: 1 Sec 内存限制: 128 MB

题目描述

佳佳对数学，尤其数列十分感兴趣，在研究完Fibonacci之后，他创造出许多稀奇古怪的数列。如求S(n)表示Fibonacci数列前n项和对m取模之后的值，即S(n)=(F1+F2+…+Fn) mod m，F1=F2=1。可是这对佳佳来说还是小菜一碟。终于，他找到一个自己解决不了的数列。。。T(n)表示Fibonacci数列前n项变形后的和对m取模之后的值，即T(n)=(F1+2*F2+3*F3+…+n*Fn) mod m，F1=F2=1。

输入

第一行，包含两个整数n和m。1<=n,m<=2^31-1

输出

共1行， T（n）的值。

样例输入

5 5

样例输出

【样例解释】

T（5）=（1+2*1+3*2+4*3+5*5）mod 5 = 1

【数据规模】

30%数据1<=n<=1000

60%数据1<=m<=1000

100%数据1<=n,m<=2^31-1