QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68601#3799. It's Surely ComplexSanguineChameleonWA 1113ms73148kbC++145.9kb2022-12-17 19:18:112022-12-17 19:18:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-17 19:18:13]
  • 评测
  • 测评结果：WA
  • 用时：1113ms
  • 内存：73148kb
查看
  • [2022-12-17 19:18:11]
  • 提交

answer

// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

long double rand_real(long double rmin, long double rmax) {
	uniform_real_distribution<long double> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int kt = 20;
const int ms = 1 << kt;
const long double pi = acos(-1);
complex<long double> fa[ms];
complex<long double> fb[ms];
int rv[ms];
long long cc[ms];
long long p, n;

complex<long long> operator%(complex<long long> x, long long y) {
	return complex<long long>((x.real() % y + y) % y, (x.imag() % y + y) % y);
}

void fft(complex<long double> a[], bool ff) {
	for (int i = 0; i < ms; i++) {
		if (i < rv[i]) {
			swap(a[i], a[rv[i]]);
		}
	}
	for (int sz = 2; sz <= ms; sz *= 2) {
		long double ang = pi * 2 / sz * (ff ? -1 : 1);
		complex<long double> pp(cos(ang), sin(ang));
		for (int i = 0; i < ms; i += sz) {
			complex<long double> cc = 1;
			for (int j = 0; j < sz / 2; j++) {
				complex<long double> t1 = a[i + j];
				complex<long double> t2 = a[i + j + sz / 2] * cc;
				a[i + j] = t1 + t2;
				a[i + j + sz / 2] = t1 - t2;
				cc *= pp;
			}
		} 
	}
	if (ff) {
		for (int i = 0; i < ms; i++) {
			a[i] /= ms;
		}
	}
}

complex<long long> bin_pow(long long x, long long y, int t) {
	long long res = 1;
	long long cc = x;
	while (y) {
		if (y & 1) {
			res = res * cc % p;
		}
		y >>= 1;
		cc = cc * cc % p;
	}
	if (t == 0) {
		return complex<long long>(res, 0);
	}
	else if (t == 1) {
		return complex<long long>(0, res);
	}
	else if (t == 2) {
		return complex<long long>((p - res) % p, 0);
	}
	else {
		return complex<long long>(0, (p - res) % p);
	}
}

complex<long long> bin_pow(complex<long long> x, __int128 y) {
	complex<long long> res(1, 0);
	complex<long long> cc(x);
	while (y) {
		if (y & 1) {
			res = (res * cc) % p;
		}
		y >>= 1;
		cc = (cc * cc) % p;
	}
	return res;
}

long long mul(long long x, long long y, long long z) {
	return (x % z * y % z) % z;
}

void just_do_it() {
	for (int i = 0; i < ms; i++) {
		for (int j = 0; j < kt; j++) {
			rv[i] |= ((i >> j) & 1) << (kt - 1 - j);
		}
	}
	cin >> p >> n;
	long long k = (n + 1) / p;
	complex<long long> res(1, 0);
	for (int i = 0; i < ms; i++) {
		fa[i] = 0;
	}
	for (int i = 0; i < (n + 1) % p; i++) {
		fa[1LL * i * i % p] += 1;
	}
	fft(fa, 0);
	for (int i = 0; i < ms; i++) {
		fa[i] *= fa[i];
	}
	fft(fa, 1);
	for (int i = 0; i < p; i++) {
		cc[i] = 0;
	}
	for (int i = 0; i < ms; i++) {
		cc[i % p] += (long long)round(fa[i].real());
	}
	for (int i = 0; i < (n + 1) % p; i++) {
		cc[1LL * i * i * 2 % p] -= 1;
	}
	if (cc[0] > 0) {
		cout << 0 << " " << 0;
		return;
	}
	for (int i = 1; i < p; i++) {
		long long y = mul(mul(cc[i] / 2, k + 1, p - 1), k + 1, p - 1);
		int t = mul(mul(cc[i] / 2, k + 1, 4), k + 1, 4);
		res *= bin_pow(i, y, t);
		res = res % p;
	}
	for (int i = 0; i < ms; i++) {
		fa[i] = 0;
	}
	for (int i = (n + 1) % p; i < p; i++) {
		fa[1LL * i * i % p] += 1;
	}
	fft(fa, 0);
	for (int i = 0; i < ms; i++) {
		fa[i] *= fa[i];
	}
	fft(fa, 1);
	for (int i = 0; i < p; i++) {
		cc[i] = 0;
	}
	for (int i = 0; i < ms; i++) {
		cc[i % p] += (long long)round(fa[i].real());
	}
	for (int i = (n + 1) % p; i < p; i++) {
		cc[1LL * i * i * 2 % p] -= 1;
	}
	if (cc[0] > 0) {
		cout << 0 << " " << 0;
		return;
	}
	for (int i = 1; i < p; i++) {
		long long y = mul(mul(cc[i] / 2, k, p - 1), k, p - 1);
		if (i == 0) {
			y = 0;
		}
		int t = mul(mul(cc[i] / 2, k, 4), k, 4);
		res *= bin_pow(i, y, t);
		res = res % p;
	}
	for (int i = 0; i < ms; i++) {
		fa[i] = 0;
		fb[i] = 0;
	}
	for (int i = 0; i < (n + 1) % p; i++) {
		fa[1LL * i * i % p] += 1;
	}
	for (int i = (n + 1) % p; i < p; i++) {
		fb[1LL * i * i % p] += 1;
	}
	fft(fa, 0);
	fft(fb, 0);
	for (int i = 0; i < ms; i++) {
		fa[i] *= fb[i];
	}
	fft(fa, 1);
	for (int i = 0; i < p; i++) {
		cc[i] = 0;
	}
	for (int i = 0; i < ms; i++) {
		cc[i % p] += (long long)round(fa[i].real());
	}
	if (cc[0] > 0) {
		cout << 0 << " " << 0;
		return;
	}
	for (int i = 1; i < p; i++) {
		long long y = mul(mul(cc[i], k, p - 1), k + 1, p - 1);
		int t = mul(mul(cc[i], k, 4), k + 1, 4);
		res *= bin_pow(i, y, t);
		res = res % p;
	}
	for (int i = 1; i < p; i++) {
		if (i < (n + 1) % p) {
			res *= bin_pow(i, mul(k + 1, k + 1, p - 1), 0);
			res = res % p;
			res = res * bin_pow(complex<long long>(1, 1), (__int128)(k + 1) * (k + 1)) % p;
		}
		else {
			res *= bin_pow(i, mul(k, k, p - 1), 0);
			res = res * bin_pow(complex<long long>(1, 1), (__int128)k * k) % p;
		}
	}
	cout << res.real() << " " << res.imag();
}

// END MAIN CODE
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1047ms
memory: 73004kb

input:

2 1

output:

1 1

result:

ok single line: '1 1'

Test #2:

score: 0
Accepted
time: 1036ms
memory: 73148kb

input:

2 2

output:

1 1

result:

ok single line: '1 1'

Test #3:

score: 0
Accepted
time: 1015ms
memory: 73148kb

input:

2 3

output:

0 0

result:

ok single line: '0 0'

Test #4:

score: 0
Accepted
time: 1056ms
memory: 73084kb

input:

2 4

output:

0 0

result:

ok single line: '0 0'

Test #5:

score: 0
Accepted
time: 1098ms
memory: 73148kb

input:

3 1

output:

2 1

result:

ok single line: '2 1'

Test #6:

score: 0
Accepted
time: 1113ms
memory: 73004kb

input:

3 2

output:

2 0

result:

ok single line: '2 0'

Test #7:

score: 0
Accepted
time: 1054ms
memory: 73028kb

input:

3 3

output:

1 0

result:

ok single line: '1 0'

Test #8:

score: 0
Accepted
time: 1051ms
memory: 73068kb

input:

3 4

output:

1 1

result:

ok single line: '1 1'

Test #9:

score: 0
Accepted
time: 1032ms
memory: 73000kb

input:

3 5

output:

1 0

result:

ok single line: '1 0'

Test #10:

score: 0
Accepted
time: 1077ms
memory: 73004kb

input:

3 6

output:

1 0

result:

ok single line: '1 0'

Test #11:

score: -100
Wrong Answer
time: 600ms
memory: 41772kb

input:

5 1

output:

0 0

result:

wrong answer 1st lines differ - expected: '4 1', found: '0 0'
English 繁體中文 简体中文

服务器时间: 2025-02-02 03:56:35 | 开源项目