acwing 205题解

具体讲解b站有.

#include <bits/stdc++.h>
using namespace std;
const int mod=10000;
void mul1(int f[2],int a[2][2])
{
    int temp[2]={0};
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            temp[i]=(temp[i]+f[j]*a[i][j])%mod;   
        }
    }
    memcpy(f,temp,sizeof temp);
}

void mul2(int a[2][2])
{
    int c[2][2]={0};
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c));

}

int main()
{
    //f[i+2]=f[i+1]+f[i].
    int n;
    while(cin>>n&&n!=-1)
    {
        int a[2][2]={
        {0,1},
        {1,1}
                };
        int f[2]={1,1};
        n--;
        while(n>0)
        {
            if(n&1) { mul1(f,a); }
            mul2(a);
            n>>=1;
        }
        if(n==-1) f[0]=0;
        cout<<f[0]<<endl;
    }
    return 0;
}