[文章目录]
Description
求Fibonacci [x,y] 的和，多组数据t<=1000,x,y不爆int。
矩乘，a[i]表示第i项Fibonacci的前缀[1,i]的前缀和，构建矩阵{a[i-2],a[i-1],a[i]}乘法矩阵：
0 0 -1
1 0 0
0 1 2然后，f(y)-f(x-1)就是解了
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define MOD 10000
using namespace std;
int x,y,t,sum1,sum2;
int a[4],b[4][4];
void work()
{
int c[4][4];
memset(c,0,sizeof(c));
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c[i][j]+=b[i][k]*b[k][j];
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
b[i][j]=c[i][j]%MOD;
}
void clear()
{
a[1]=0;a[2]=1;a[3]=2;
b[1][1]=0;b[1][2]=0;b[1][3]=-1;
b[2][1]=1;b[2][2]=0;b[2][3]=0;
b[3][1]=0;b[3][2]=1;b[3][3]=2;
}
void doit()
{
int c[4];
memset(c,0,sizeof(c));
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
c[i]+=a[j]*b[j][i];
for(int i=1;i<=3;i++)
a[i]=c[i]%MOD;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&x,&y);
x--;
clear();
while(x)
{
if(x&1)
doit();
work();
x>>=1;
}
sum1=a[1];
clear();
while(y)
{
if(y&1)
doit();
work();
y>>=1;
}
sum2=a[1];
printf("%d\n",((sum2-sum1)%MOD+MOD)%MOD);
}
return 0;
}