【NOIP2016提高A组模拟9.24】天使的分裂

Description

简化后的题意：
已知斐波那契数列

f0=f1=1

fi=f[i−1]+f[i−2]

和一个函数

Fn=∑i=0nf[i]∗f[n−i]

注意小f和大F的区别
求

∑i=0nF[i]

Input

一个整数n

Output

一行，一个整数，表示第0天到第n天的评估函数的值的和。

Sample Input

Input 1
5
Input 2
666666
Input 3
2147483648

Sample Output

Output 1
76
Output 2
324016098
Output 3
932937567

Data Constraint

n<=1018

Solution

看到n的大小，显然矩阵乘法
先推方程

Fn=∑i=0n(f[i]∗f[n−i])

=∑i=2n(f[i−1]+f[i−2])∗f[n−i]+f[0]∗f[n−1]+f[1]∗f[n]

因为 f[i]=f[i−1]+f[i−2]
所以括号里的东西就是f[i]，加上括号外的就与前面等价
乘法分配乘到括号外就变成了
f[i−1]∗f[n−i] 和 f[i−2]∗f[n−i] 也就是 F[n−1]−f[n−1] 和 F[n−2]
由于 f[0]=f[1]=1
所以后面的就变成了 f[n−1]−f[n−1]+f[n]=f[n]
所以总共就是

F[n]=F[n−1]+F[n−2]+f[n]

然后记录好F的前缀和，5*5的矩阵就行了，自己推
不想推的看程序

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 1010000
#define ll long long
#define mo 998244353ll
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
ll c[5][5],a[5][5],f[5][5],ans=0,n;
ll b[5][5]={{0,1,0,1,1},{1,1,0,1,1},{0,0,0,1,1},{0,0,1,1,1},{0,0,0,0,1}};
void mi(ll d)
{
 ll e[60],l=0;
 for(;d>1;d/=2) e[++l]=d%2;
 for(;l>0;l--)
 {
 cl(c);
 fo(i,0,4) fo(j,0,4) fo(k,0,4) c[i][k]=(c[i][k]+b[i][j]*b[j][k])%mo;
 cl(b);
 if(e[l]==1)
 {
 fo(i,0,4) fo(j,0,4) fo(k,0,4) b[i][k]=(b[i][k]+c[i][j]*a[j][k])%mo;
 }
 else
 {
 fo(i,0,4) fo(j,0,4) b[i][j]=c[i][j];
 }
 }
}
int main()
{
 scanf("%lld",&n);
 fo(i,0,4) fo(j,0,4) a[i][j]=b[i][j];
 mi(n);cl(c);f[0][0]=0;f[0][1]=1;f[0][2]=0;f[0][3]=1;f[0][4]=1;
 fo(j,0,4) fo(k,0,4) c[0][k]=(c[0][k]+f[0][j]*b[j][k])%mo;
 if(n==0) printf("1\n"); else printf("%lld",c[0][4]);
}