QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#29883#2897. Circle BounceGeorge_Plover#AC ✓4ms3664kbC++1.6kb2022-04-23 12:41:202022-04-28 15:57:46

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 15:57:46]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3664kb
  • [2022-04-23 12:41:20]
  • Submitted

answer

#include <bits/stdc++.h>

#define M 1000000007

using namespace std;

struct mat
{
    int v[2][2];

    mat(bool d = false)
    {
        v[0][0] = v[1][1] = d;
        v[0][1] = v[1][0] = 0;
    }

    mat operator*(const mat &m) const
    {
        auto r = mat();
        r.v[0][0] = ((long long)v[0][0] * m.v[0][0] + (long long)v[0][1] * m.v[1][0]) % M;
        r.v[0][1] = ((long long)v[0][0] * m.v[0][1] + (long long)v[0][1] * m.v[1][1]) % M;
        r.v[1][0] = ((long long)v[1][0] * m.v[0][0] + (long long)v[1][1] * m.v[1][0]) % M;
        r.v[1][1] = ((long long)v[1][0] * m.v[0][1] + (long long)v[1][1] * m.v[1][1]) % M;
        return r;
    }

    mat operator^(long long e) const
    {
        auto r = mat(true);

        for (mat x = *this; e; e >>= 1, x = x * x)
            if (e & 1)
                r = r * x;

        return r;
    }
} z;

long long n;
int a, b, c;

int inv(int x) { return x < 2 ? x : (M - M / x * (long long)inv(M % x) % M) % M; }

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> n;
    c = inv(((long long)a * a + (long long)b * b) % M);
    z.v[0][0] = z.v[1][1] = ((long long)a * a % M + M - (long long)b * b % M) % M * c % M;
    z.v[0][1] = 2LL * a * b % M * c % M;
    z.v[1][0] = (M - z.v[0][1]) % M;
    // cerr << z.v[0][0] << ' ' << z.v[0][1] << '\n'
    //      << z.v[1][0] << ' ' << z.v[1][1] << '\n';
    z = z ^ (n + 1);
    // cerr << z.v[0][0] << ' ' << z.v[0][1] << '\n'
    //      << z.v[1][0] << ' ' << z.v[1][1] << '\n';
    cout << ((M - z.v[1][1]) % M) << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

999999998 999999999 1000000000

output:

86174826

result:

ok single line: '86174826'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3604kb

input:

314159265 1414213 31413413

output:

174644643

result:

ok single line: '174644643'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

355 113 1000000000000

output:

964036762

result:

ok single line: '964036762'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

267204667 335545842 696754506694

output:

869642485

result:

ok single line: '869642485'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

608585399 831320119 672380354760

output:

16481017

result:

ok single line: '16481017'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

376844222 336360777 909739767563

output:

610206681

result:

ok single line: '610206681'

Test #7:

score: 0
Accepted
time: 4ms
memory: 3596kb

input:

812478595 209900954 868059762327

output:

396736907

result:

ok single line: '396736907'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3628kb

input:

508794642 851378491 104036237152

output:

843802314

result:

ok single line: '843802314'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1 1 3

output:

1000000006

result:

ok single line: '1000000006'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3572kb

input:

1 2 1

output:

960000007

result:

ok single line: '960000007'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

11 63 44

output:

22

result:

ok single line: '22'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3600kb

input:

163 713 980

output:

0

result:

ok single line: '0'