sdnu1313 Chess （找规律 斐波那契+矩阵快速幂模板）

Description

小X有一个1*n的跳棋棋盘。今天小X要去参加比赛，他希望所有的跳棋排成他希望的队形（即在指定的格子上有棋子）来给他加油。小X只能在棋盘的第1个格或第2个格放置棋子，而其他的格子只能通过跳棋的跳跃到达。当且仅当第i格有棋子，i+1格有棋子，i+2格为空的时候，i格上的棋子能够跳到i+2格上，与此同时i+1格子上的棋子会消失。同理，当且仅当第i格有棋子，i-1格有棋子，i-2格为空的时候，i格上的棋子能够跳到i-2格上，与此同时i-1格子上的棋子会消失。

现在告诉你小X希望那些格子上需要有棋子，你的任务是求出最少需要在棋盘上放置多少个棋子才能做到。

由于这个答案可能过大，为了简化问题，你只需要输出最终答案模268435456的余数。

Input

第一行2个整数：n，m。n表示棋盘的大小，m表示希望放置棋子的格子个数。2<n<=100000，m<=n。所有的a∈[3,n]，保证按非减序给出。

接下来m行，每行一个整数a，表示在第a个格子上需要放置一枚棋子。

Output

一个整数，最少需要放置的棋子数量 mod 268435456。

Sample Input

4 2
3 
4

Sample Output

5

不难发现f(n)=f(n-1)+f(n-2)  1e5的数据 递推会超时的 正好学一下矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2;
const int MOD=268435456;
struct mat
{
    ll a[N][N];
};
mat mat_mul(mat x,mat y)
{
    mat res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
    return res;
}
long long mat_pow(ll n)
{
    mat c,res;
    c.a[0][0]=c.a[0][1]=c.a[1][0]=1;
    c.a[1][1]=0;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++)
        res.a[i][i]=1;
    while(n)
    {
        if(n&1)
            res=mat_mul(res,c);
        c=mat_mul(c,c);
        n=n>>1;
    }
    return res.a[0][1];
}
int main()
{
    ll n;
    int a,b;
    scanf("%d%d",&a,&b);
    long long ans=0;
    while(b--)
    {
        scanf("%lld",&n);
        long long tmp=mat_pow(n);
        ans=(ans%MOD+tmp%MOD)%MOD;
    }
    cout<<ans<<'\n';
    return 0;
}