aoj2372:IkaNumber

問題文

IkaNumber | Aizu Online Judge

解法

フィボナッチ数列を
1,1,2,3,5,...
とし、添え字は0から始まるものとする。

F(n):n番目のフィボナッチ数、とする

例：F(1)=1 , F(2)=2 ,F(5)=8

にんじんがない場合は、通り数はフィボナッチ数のどれかになる。
にんじんがある場合、適当に紙に書いて考えてみると、通り数は一般に
F(k)*F(l) (k,lは自然数(0は自然数でわない))
となる。

あとは実験すると解ける

コード

#include<bits/stdc++.h>
using namespace std;


#define int long long


#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;

typedef vector<vint>mat;

mat mul(mat A,mat B){
    mat C(A.size(),vint(B[0].size()));

    for(int i=0;i<A.size();i++){
        for(int j=0;j<B[0].size();j++){
            for(int k=0;k<A[0].size();k++){
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }

    return C;
}

mat matpow(mat A,int k){
    mat B(A.size(),vint(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    while(k){
        if(k&1)B=mul(B,A);
        A=mul(A,A);
        k>>=1;
    }
    return B;
}

int F(int n){
    mat A(2,vint(2));
    A[0][0]=1;A[0][1]=1;
    A[1][0]=1;A[1][1]=0;

    mat X(2,vint(1));
    X[0][0]=1;X[1][0]=0;

    X=mul(matpow(A,n),X);
    return X[0][0];
}

signed main(){
    /*
    for(int i=2;i<=20;i++){
        for(int j=1;i-j>=1;j++){
            cout<<F(j)*F(i-j)<<" ";
        }cout<<endl;
    }*/

    int K;
    cin>>K;
    int lb=0,ub=1000000000;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(mid*(mid+1)<K)lb=mid;
        else ub=mid;
    }

    K-=lb*(lb+1);

    int s=ub*2;

    if(K>ub){
        K-=ub;
        s++;
    }


    int t=s/2;
    int w;
    if(K<=(t+1)/2){
        w=K*2-1;
    }
    else{
        K=t-K+1;
        w=K*2;
    }
    cout<<F(w)*F(s-w)%mod<<endl;

    return 0;
}