First of all, thank you. I changed my code, then it works well for your test case. But I got WA again, please give me a hint to find mistake again.
My code (after changes) is:
#include <bits/stdc++.h>
#define PII pair<ll,ll>
typedef long long ll;
using namespace std;
const ll EPS=1e9+7;
PII fib(ll n)
{
if(n==0)
return {0, 1};
auto p=fib(n >> 1);
ll c=((p.first%EPS)*((2*(p.second%EPS))%EPS-p.first%EPS)%EPS)%EPS; // this line was changed
ll d=((p.first%EPS)*(p.first%EPS))%EPS+((p.second%EPS)*(p.second%EPS))%EPS; // this line was changed
if(n&1)
return {d, (c + d)%EPS};
else
return {c, d};
}
int main()
{
ll t,n;
cin>>t;
while(t–)
{
cin>>n;
PII ans=fib(n+1);
if(n==0)
cout<<0<<endl; // this line was changed
else if(n==1)
cout<<2<<endl;
else
cout<<(ans.first%EPS+ans.second%EPS)%EPS<<endl;
}
return 0;
}
Thank you Simes in advance.