Aug 2019
1 / 10
Aug 2019
Dec 2021
fcb2000
Aug '19
1

Can anybody help me to find my mistake in order to solve the problem easily, please. I got WA from this problem.
Link of the problem is https://www.spoj.com/problems/MAIN74/24 .

My code 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);
int c=((p.first%EPS)*((2*(p.second%EPS))%EPS-p.first%EPS)%EPS)%EPS;
int d=((p.first%EPS)*(p.first%EPS))%EPS+((p.second%EPS)*(p.second%EPS))%EPS;
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;
else if(n==1)
cout<<2<<endl;
else
cout<<(ans.first%EPS+ans.second%EPS)%EPS<<endl;
}
return 0;
}

Please help me…

  • created

    Aug '19

  • last reply

    Dec '21
  • 9

    replies

  • 1.6k

    views

  • 5

    users

  • 1

    like

  • 2

    links

simes
Aug '19

Here are a couple of test cases:

2
100000000000000
1000000000000000000

Expected answer:

226451933
569898238

fcb2000
Aug '19

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.

fcb2000
Aug '19

First of all, I’m glad to see helpful test case from you. THANK YOU. After your test case, I eventually have achieved AC despite having many WAs. You are the best and most helpful competetive programmer I have ever seen. THANKS AGAIN for your CONSIDERATION(attention).
:clap: :clap: :clap:

7 months later
simes
Mar '20

It’s so unbecoming to beg.

If it were up to me, I’d say fcb2000 should not post the AC code. If it were up to me, the non-AC code would be removed too. There are too many people willing to copy’n’paste complete solutions, and nobody benefits from that.

You’ve only made one submission, perhaps you should try a little harder?

abuzahid
Mar '20
simes

Getting the following output for this test case:

588214857

Still getting WA.

Any idea, please??

1 year later
samrat2825
Dec '21
simes
#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll mod = 1e9+7;

pair<ll,ll> fib(ll n)
{
if(n == 0)
return {01LL,11LL};

auto p = fib(n>>1);
p = {p.first%mod,p.second%mod};
ll c = (p.first*(((2*p.second)%mod-p.first)%mod))%mod;
ll d = ((p.first*p.first)%mod+(p.second*p.second)%mod)%mod;

if(n&1)return {d,(c+d)%mod};
else    return {c,d};

}

int main() {

ll t;
cin>>t;

while(t--)
{
    ll n;
    cin>>n;
    
    if(n<0)
        {
            cout<<"0"<<endl;
            continue;
        }
    else if(n == 0)
    {
        cout<<"1"<<endl;
        continue;
    }
    else if(n == 1)
    {
        cout<<"2"<<endl;
        continue;
    }
    else
    {
        auto ans = fib(n+1);
        cout<<(ans.first%mod+ans.second%mod)%mod<<endl;
    }
}

return 0;

}

Can you tell me what I am doing wrong?