NOI2016 山西省省选第二题序列

给出一个n（n<=10^18）然后把n拆成若干个数之和(3=1+2=2+1 是两种情况) 然后把这写数字当作斐波那契数列的下标相乘再相加

例如:

3=1+1+1=1+2=2+1=3

所以结果就是

F₁*F₁*F₁+F₁*F₂+F₂*F₁+F₃=5

首先先试一试，找规律

不难发现

G_n=2*G_n-1+G_n-2

但是10^18次方比较猥琐纯递推貌似只能得70

然后考虑矩阵乘法

构建一个矩阵用来递推

2 1

1 0

就可以了，比较类似poj3070那倒题

//这是一个有趣的斐波那契数列的计算，矩阵乘法加速递推   这样子可以混搭快速幂 速度高 10^18次

//应该能过

/*

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int n;

void cheng (int a[2][2],int b[2][2])

{

    int c[2][2];

    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]*b[k][j])%10000;

    memcpy(a,c,sizeof(c));

}

int main()

{

    while (cin>>n && n!=-1)

    {

        int f[2][2]={{0,1},{0,0}};

        int a[2][2]={{0,1},{1,1}};

        while (n>0)

     {

         if(n&1) cheng(f,a);

         cheng (a,a);

         n>>=1;

     }

      printf("%d\n",f[0][0]);

    }

}

*/

//稍微改一改 其实数据再多一点的话unsigned long long 估计就会炸了就需要用高精度了 

#include <cstdio>

#include <iostream>

#include <cstring>

#define MOD 1000000007

using namespace std;

unsigned long long n;

long long f[][]={{,},{,}};

long long a[][]={{,},{,}};

void cheng (long long a[][],long long b[][])

{

    long long c[][];

    memset(c,,sizeof(c));

    for (int i=;i<;i++)

        for (int j=;j<;j++)

          for (int k=;k<;k++)

              c[i][j]+=((a[k][j]%MOD)*(b[i][k]%MOD))%MOD;

    memcpy(a,c,sizeof(c));

}

int main()

{

    cin>>n;

    if (n==){

        printf("0\n");

        return ;

    }

    --n;

    while (n)

    {

         if(n&) cheng(f,a);

         cheng (a,a);

         n>>=;

    }

    printf("%d\n",f[][]);

}

就这样就可以了，但貌似考场上程序忘了处理0的情况了/泪目

NOI2016 山西省省选 第二题序列

NOI2016 山西省省选第二题序列