QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68602#3799. It's Surely ComplexSanguineChameleonAC ✓3942ms78264kbC++146.0kb2022-12-17 19:20:422022-12-17 19:20:43

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:20:43]
  • 评测
  • 测评结果：AC
  • 用时：3942ms
  • 内存：78264kb
查看
  • [2022-12-17 19:20:42]
  • 提交

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;
	}
	if (k > 0) {
		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: 1034ms
memory: 73008kb

input:

2 1

output:

1 1

result:

ok single line: '1 1'

Test #2:

score: 0
Accepted
time: 1020ms
memory: 73080kb

input:

2 2

output:

1 1

result:

ok single line: '1 1'

Test #3:

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

input:

2 3

output:

0 0

result:

ok single line: '0 0'

Test #4:

score: 0
Accepted
time: 1034ms
memory: 73076kb

input:

2 4

output:

0 0

result:

ok single line: '0 0'

Test #5:

score: 0
Accepted
time: 312ms
memory: 41540kb

input:

3 1

output:

2 1

result:

ok single line: '2 1'

Test #6:

score: 0
Accepted
time: 1027ms
memory: 73080kb

input:

3 2

output:

2 0

result:

ok single line: '2 0'

Test #7:

score: 0
Accepted
time: 1100ms
memory: 72996kb

input:

3 3

output:

1 0

result:

ok single line: '1 0'

Test #8:

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

input:

3 4

output:

1 1

result:

ok single line: '1 1'

Test #9:

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

input:

3 5

output:

1 0

result:

ok single line: '1 0'

Test #10:

score: 0
Accepted
time: 1079ms
memory: 73152kb

input:

3 6

output:

1 0

result:

ok single line: '1 0'

Test #11:

score: 0
Accepted
time: 330ms
memory: 41352kb

input:

5 1

output:

4 1

result:

ok single line: '4 1'

Test #12:

score: 0
Accepted
time: 329ms
memory: 40760kb

input:

5 2

output:

0 0

result:

ok single line: '0 0'

Test #13:

score: 0
Accepted
time: 318ms
memory: 40972kb

input:

5 3

output:

0 0

result:

ok single line: '0 0'

Test #14:

score: 0
Accepted
time: 623ms
memory: 41680kb

input:

5 4

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0
Accepted
time: 635ms
memory: 41096kb

input:

5 5

output:

0 0

result:

ok single line: '0 0'

Test #16:

score: 0
Accepted
time: 627ms
memory: 41276kb

input:

5 6

output:

0 0

result:

ok single line: '0 0'

Test #17:

score: 0
Accepted
time: 338ms
memory: 41536kb

input:

5 7

output:

0 0

result:

ok single line: '0 0'

Test #18:

score: 0
Accepted
time: 341ms
memory: 41432kb

input:

5 8

output:

0 0

result:

ok single line: '0 0'

Test #19:

score: 0
Accepted
time: 631ms
memory: 42104kb

input:

5 9

output:

0 0

result:

ok single line: '0 0'

Test #20:

score: 0
Accepted
time: 668ms
memory: 42216kb

input:

5 10

output:

0 0

result:

ok single line: '0 0'

Test #21:

score: 0
Accepted
time: 359ms
memory: 42236kb

input:

7 1

output:

6 1

result:

ok single line: '6 1'

Test #22:

score: 0
Accepted
time: 361ms
memory: 42220kb

input:

7 2

output:

3 0

result:

ok single line: '3 0'

Test #23:

score: 0
Accepted
time: 317ms
memory: 41600kb

input:

7 3

output:

2 5

result:

ok single line: '2 5'

Test #24:

score: 0
Accepted
time: 308ms
memory: 42060kb

input:

7 4

output:

1 0

result:

ok single line: '1 0'

Test #25:

score: 0
Accepted
time: 301ms
memory: 40940kb

input:

7 5

output:

5 2

result:

ok single line: '5 2'

Test #26:

score: 0
Accepted
time: 1035ms
memory: 73012kb

input:

7 6

output:

6 0

result:

ok single line: '6 0'

Test #27:

score: 0
Accepted
time: 1048ms
memory: 73152kb

input:

7 7

output:

1 0

result:

ok single line: '1 0'

Test #28:

score: 0
Accepted
time: 1073ms
memory: 73156kb

input:

7 8

output:

4 4

result:

ok single line: '4 4'

Test #29:

score: 0
Accepted
time: 1048ms
memory: 73188kb

input:

7 9

output:

4 0

result:

ok single line: '4 0'

Test #30:

score: 0
Accepted
time: 1006ms
memory: 73144kb

input:

7 10

output:

2 2

result:

ok single line: '2 2'

Test #31:

score: 0
Accepted
time: 1019ms
memory: 73152kb

input:

7 11

output:

1 0

result:

ok single line: '1 0'

Test #32:

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

input:

7 12

output:

4 4

result:

ok single line: '4 4'

Test #33:

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

input:

7 13

output:

1 0

result:

ok single line: '1 0'

Test #34:

score: 0
Accepted
time: 1028ms
memory: 73080kb

input:

7 14

output:

1 0

result:

ok single line: '1 0'

Test #35:

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

input:

2 1000000000000000000

output:

0 0

result:

ok single line: '0 0'

Test #36:

score: 0
Accepted
time: 1048ms
memory: 73152kb

input:

3 1000000000000000000

output:

1 1

result:

ok single line: '1 1'

Test #37:

score: 0
Accepted
time: 3942ms
memory: 78264kb

input:

499979 1000000000000000000

output:

486292 0

result:

ok single line: '486292 0'

Test #38:

score: 0
Accepted
time: 310ms
memory: 44992kb

input:

499973 1000000000000000000

output:

0 0

result:

ok single line: '0 0'

Test #39:

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

input:

2 576460752303423488

output:

0 0

result:

ok single line: '0 0'

Test #40:

score: 0
Accepted
time: 1095ms
memory: 73152kb

input:

3 864691128455135232

output:

1 0

result:

ok single line: '1 0'

Test #41:

score: 0
Accepted
time: 301ms
memory: 41252kb

input:

43 41

output:

32 11

result:

ok single line: '32 11'

Test #42:

score: 0
Accepted
time: 617ms
memory: 41288kb

input:

89 646243632056227082

output:

0 0

result:

ok single line: '0 0'

Test #43:

score: 0
Accepted
time: 1058ms
memory: 73188kb

input:

79 3818048575756175

output:

61 18

result:

ok single line: '61 18'

Test #44:

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

input:

43 417918461

output:

1 0

result:

ok single line: '1 0'

Test #45:

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

input:

67 9225777529942049

output:

26 0

result:

ok single line: '26 0'

Test #46:

score: 0
Accepted
time: 327ms
memory: 41112kb

input:

29 1894616718601

output:

0 0

result:

ok single line: '0 0'

Test #47:

score: 0
Accepted
time: 307ms
memory: 41680kb

input:

73 24891833259

output:

0 0

result:

ok single line: '0 0'

Test #48:

score: 0
Accepted
time: 293ms
memory: 41960kb

input:

751 45

output:

36 715

result:

ok single line: '36 715'

Test #49:

score: 0
Accepted
time: 1079ms
memory: 73152kb

input:

631 870852734504724166

output:

101 0

result:

ok single line: '101 0'

Test #50:

score: 0
Accepted
time: 1030ms
memory: 73012kb

input:

479 939006

output:

52 0

result:

ok single line: '52 0'

Test #51:

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

input:

503 223239772447

output:

381 0

result:

ok single line: '381 0'

Test #52:

score: 0
Accepted
time: 316ms
memory: 42428kb

input:

317 73782933513241136

output:

0 0

result:

ok single line: '0 0'

Test #53:

score: 0
Accepted
time: 286ms
memory: 40944kb

input:

577 4897864747011

output:

0 0

result:

ok single line: '0 0'

Test #54:

score: 0
Accepted
time: 1053ms
memory: 73152kb

input:

571 7326187013

output:

400 171

result:

ok single line: '400 171'

Test #55:

score: 0
Accepted
time: 285ms
memory: 41972kb

input:

9787 39

output:

953 8834

result:

ok single line: '953 8834'

Test #56:

score: 0
Accepted
time: 296ms
memory: 41092kb

input:

4177 296229723194145403

output:

0 0

result:

ok single line: '0 0'

Test #57:

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

input:

5039 71501150263015946

output:

4425 4425

result:

ok single line: '4425 4425'

Test #58:

score: 0
Accepted
time: 994ms
memory: 73120kb

input:

7027 44142

output:

6075 0

result:

ok single line: '6075 0'

Test #59:

score: 0
Accepted
time: 280ms
memory: 41796kb

input:

1877 5605079

output:

0 0

result:

ok single line: '0 0'

Test #60:

score: 0
Accepted
time: 294ms
memory: 40464kb

input:

2251 187

output:

1847 404

result:

ok single line: '1847 404'

Test #61:

score: 0
Accepted
time: 296ms
memory: 40660kb

input:

3863 699

output:

3850 13

result:

ok single line: '3850 13'

Test #62:

score: 0
Accepted
time: 313ms
memory: 41556kb

input:

92557 64

output:

28440 0

result:

ok single line: '28440 0'

Test #63:

score: 0
Accepted
time: 1372ms
memory: 73560kb

input:

62047 410196757795686372

output:

11479 11479

result:

ok single line: '11479 11479'

Test #64:

score: 0
Accepted
time: 306ms
memory: 40852kb

input:

67129 2833304630

output:

0 0

result:

ok single line: '0 0'

Test #65:

score: 0
Accepted
time: 304ms
memory: 42324kb

input:

90793 25188225487855

output:

0 0

result:

ok single line: '0 0'

Test #66:

score: 0
Accepted
time: 301ms
memory: 41752kb

input:

55313 111467

output:

0 0

result:

ok single line: '0 0'

Test #67:

score: 0
Accepted
time: 1270ms
memory: 75624kb

input:

69151 718198020401

output:

9621 59530

result:

ok single line: '9621 59530'

Test #68:

score: 0
Accepted
time: 1038ms
memory: 75376kb

input:

48571 56301

output:

2628 0

result:

ok single line: '2628 0'

Test #69:

score: 0
Accepted
time: 325ms
memory: 44412kb

input:

326983 51

output:

39793 287190

result:

ok single line: '39793 287190'

Test #70:

score: 0
Accepted
time: 3436ms
memory: 76328kb

input:

406183 933021611983655873

output:

238788 167395

result:

ok single line: '238788 167395'

Test #71:

score: 0
Accepted
time: 289ms
memory: 41512kb

input:

152729 7971425537345

output:

0 0

result:

ok single line: '0 0'

Test #72:

score: 0
Accepted
time: 321ms
memory: 43132kb

input:

183047 6977

output:

141264 41783

result:

ok single line: '141264 41783'

Test #73:

score: 0
Accepted
time: 301ms
memory: 44412kb

input:

207973 3240

output:

0 0

result:

ok single line: '0 0'

Test #74:

score: 0
Accepted
time: 1464ms
memory: 76132kb

input:

141907 10497585978

output:

141777 141777

result:

ok single line: '141777 141777'

Test #75:

score: 0
Accepted
time: 276ms
memory: 44476kb

input:

279317 6562

output:

0 0

result:

ok single line: '0 0'
English 繁體中文 简体中文

伺服器時間: 2025-02-01 23:03:17 | 開源專案