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[]);
    }
}