QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224977 | #2897. Circle Bounce | PetroTarnavskyi# | AC ✓ | 0ms | 3728kb | C++17 | 1.6kb | 2023-10-23 19:13:44 | 2023-10-23 19:13:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 1'000'000'007;
int add(int a, int b)
{
return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
return (LL)a * b % mod;
}
int binpow(int a, LL n)
{
int res = 1;
while (n)
{
if (n & 1)
res = mult(res, a);
a = mult(a, a);
n >>= 1;
}
return res;
}
int inv(int a)
{
return binpow(a, mod - 2);
}
struct Complex
{
int a, b;
Complex operator*(const Complex& z) const
{
return {sub(mult(a, z.a), mult(b, z.b)), add(mult(a, z.b), mult(z.a, b))};
}
};
Complex binpow(Complex z, LL n)
{
Complex res = {1, 0};
while (n)
{
if (n & 1)
res = res * z;
z = z * z;
n >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int a, b;
LL n;
cin >> a >> b >> n;
int a2 = mult(a, a), b2 = mult(b, b);
int x1 = mult(sub(b2, a2), inv(add(a2, b2)));
int y1 = mult(mult(2, mult(a, b)), inv(add(a2, b2)));
int A = mult(mod - 1, x1);
int B = mult(mod - 1, y1);
cout << mult(mod - 1, binpow({A, B}, n + 1).a) << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
999999998 999999999 1000000000
output:
86174826
result:
ok single line: '86174826'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
314159265 1414213 31413413
output:
174644643
result:
ok single line: '174644643'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
355 113 1000000000000
output:
964036762
result:
ok single line: '964036762'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
267204667 335545842 696754506694
output:
869642485
result:
ok single line: '869642485'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
608585399 831320119 672380354760
output:
16481017
result:
ok single line: '16481017'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
376844222 336360777 909739767563
output:
610206681
result:
ok single line: '610206681'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
812478595 209900954 868059762327
output:
396736907
result:
ok single line: '396736907'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
508794642 851378491 104036237152
output:
843802314
result:
ok single line: '843802314'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 1 3
output:
1000000006
result:
ok single line: '1000000006'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 2 1
output:
960000007
result:
ok single line: '960000007'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
11 63 44
output:
22
result:
ok single line: '22'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
163 713 980
output:
0
result:
ok single line: '0'