JZOJ4854【NOIP2016提高A組集訓第6場11.3】小澳的坐标系

Description

小澳者表也，數學者景也，表動則景随矣。

小澳不喜歡數學，可數學卻待小澳如初戀，小澳睡覺的時候也不放過。

小澳的夢境中出現了一個平面直角坐标系，自原點，向四方無限延伸。

小澳在坐标系的原點，他可以向上、向左或者向右走。他可以走n步，但不能經過相同的點。

小澳想知道他有多少種走法。

Data Constraint

n<=109

Solution

我們設F[i]表示走i步有多少種走法，那麼F[i]顯然和F[i-1]有關。經過找規律後發現F[i]=2*F[i-1]+F[i-2]。那麼打個矩陣乘法即可。

code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll mo=+;
struct code{
    ll a[][];
}b,c,d;
ll n,i,t,j,k,l,ans,f[],g[];
code make(code x,code y){
    memset(d.a,,sizeof(d.a));
    for (i=;i<;i++)
        for (j=;j<;j++)
            for (k=;k<;k++)
                d.a[i][j]=(d.a[i][j]+x.a[i][k]*y.a[k][j]%mo)%mo;
    return d;
}
code mi(int x){
    if (x==) return c;
    code d=mi(x/);
    if (x%) return make(make(d,d),c);return make(d,d);
}
int main(){
    freopen("coordinate.in","r",stdin);freopen("coordinate.out","w",stdout);
    scanf("%d",&n);
    f[]=;
    f[]=;
    if (!n) printf("%d\n",);
    else if (n==) printf("%d\n",);
    else{
        c.a[][]=,c.a[][]=c.a[][]=;
        b=mi(n-);
        i=;
        for (j=;j<;j++)
            for (k=;k<;k++)
                g[j]=(g[j]+f[k]*b.a[k][j]%mo)%mo;
        printf("%d\n",g[]);
    }
}