QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224977#2897. Circle BouncePetroTarnavskyi#AC ✓0ms3728kbC++171.6kb2023-10-23 19:13:442023-10-23 19:13:44

Judging History

This is the latest submission verdict.

  • [2023-10-23 19:13:44]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3728kb
  • [2023-10-23 19:13:44]
  • Submitted

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'