没错
by Erina @ 2017-10-19 10:08:48
现在解决了，fast\_pow(int p)那里应该改成long long p
by 白桦树 @ 2017-10-19 10:28:24
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
long long mo=1e9+7,t;
struct ju{
long long m[110][110];
}E,a,sum;
ju mul(ju q,ju w,int n,int ooo)
{
ju c;
for(int i=0;i<n;i++)
for(int j=0;j<ooo;j++)
{
c.m[i][j]=0;
for(int k=0;k<ooo;k++)
c.m[i][j]=(c.m[i][j]+(q.m[i][k]*w.m[k][j])%mo)%mo;
}
return c;
}
ju fast(ju b,long long o)
{
sum=E;
while(o)
{
if(o&1) sum=mul(sum,b,3,3);
b=mul(b,b,3,3);
o>>=1;
}
return sum;
}
int main()
{
a.m[0][0]=a.m[1][0]=a.m[0][1]=a.m[1][2]=1;
for(int i=0;i<3;i++)
E.m[i][i]=1;
ju ans;
ans.m[0][0]=2;ans.m[0][1]=1;ans.m[0][2]=1;
int k;
scanf("%d",&k);
if(k<=2) printf("1");
else
{
ju answer=mul(ans,fast(a,k-2),1,3);
printf("%lld",answer.m[0][1]);
}
return 0;
}
蜜汁80分...同楼主
```
by 我是大傻逼 @ 2017-11-01 16:57:35
注意每一个都开long long
n和快速幂里存次数的都要开long long
by memset0 @ 2017-12-17 14:39:21
#include<cstdio>
using namespace std;
const long long MOD=1000000007;
struct Fib
{
long long a[2][2];
Fib operator*(const Fib&b)
{
Fib c;
c.a[0][0]=(a[0][0]*b.a[0][0]%MOD+a[0][1]*b.a[1][0]%MOD)%MOD;
c.a[0][1]=(a[0][0]*b.a[0][1]%MOD+a[0][1]*b.a[1][1]%MOD)%MOD;
c.a[1][0]=(a[1][0]*b.a[0][0]%MOD+a[1][1]*b.a[1][0]%MOD)%MOD;
c.a[1][1]=(a[1][0]*b.a[0][1]%MOD+a[1][1]*b.a[1][1]%MOD)%MOD;
return c;
}
}A[40],ans;
long long n;
int main()
{
scanf("%lld",&n);
n--;
A[0].a[0][0]=A[0].a[0][1]=A[0].a[1][0]=1;
for(long long i=1;((long long)1<<i)<=n;i++)
A[i]=A[i-1]*A[i-1];
ans.a[0][0]=ans.a[1][1]=1;
for(long long i=0;((long long)1<<i)<=n;i++)
if(((long long)1<<i)&n)
ans=ans*A[i];
printf("%lld\n",ans.a[0][0]);
return 0;
}
虽然整个程序中一个int都找不到了，但仍然只有80分，WA的还一样。
测试点2：On line 1 column 1, read 70712, expected 18836. 得分0
测试点10：On line 1 column 1, read 1, expected 55103. 得分0
by wucstdio @ 2018-02-23 08:26:34
```cpp
#include<cstdio>
using namespace std;
const long long MOD=1000000007;
struct Fib
{
long long a[2][2];
Fib operator*(const Fib&b)
{
Fib c;
c.a[0][0]=(a[0][0]*b.a[0][0]%MOD+a[0][1]*b.a[1][0]%MOD)%MOD;
c.a[0][1]=(a[0][0]*b.a[0][1]%MOD+a[0][1]*b.a[1][1]%MOD)%MOD;
c.a[1][0]=(a[1][0]*b.a[0][0]%MOD+a[1][1]*b.a[1][0]%MOD)%MOD;
c.a[1][1]=(a[1][0]*b.a[0][1]%MOD+a[1][1]*b.a[1][1]%MOD)%MOD;
return c;
}
}A[40],ans;
long long n;
int main()
{
scanf("%lld",&n);
n--;
A[0].a[0][0]=A[0].a[0][1]=A[0].a[1][0]=1;
for(long long i=1;((long long)1<<i)<=n;i++)
A[i]=A[i-1]*A[i-1];
ans.a[0][0]=ans.a[1][1]=1;
for(long long i=0;((long long)1<<i)<=n;i++)
if(((long long)1<<i)&n)
ans=ans*A[i];
printf("%lld\n",ans.a[0][0]);
return 0;
}
```
虽然整个程序中一个int都找不到了，但仍然只有80分，WA的还一样。
测试点2：On line 1 column 1, read 70712, expected 18836. 得分0 测试点10：On line 1 column 1, read 1, expected 55103. 得分0
by wucstdio @ 2018-02-23 08:28:10