QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#29883 | #2897. Circle Bounce | George_Plover# | AC ✓ | 4ms | 3664kb | C++ | 1.6kb | 2022-04-23 12:41:20 | 2022-04-28 15:57:46 |
Judging History
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;
}
詳細信息
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'