rt

题目

WA Code

#include <bits/stdc++.h>
using namespace std;
const long long int N = 2005, mod = 2000000000000000003;
__int128 f[N];
void print(__int128 num) {
if (num > 9) print(num / 10);
putchar(num % 10 + '0');
}
/*inline __int128 dfs(__int128 num) {
	cout << num << " " << f[num] << '\n';
	if (num <= 4) return num; 
	if (f[num] != -1) return (f[num] % mod);
	__int128 lim = (num >> 1), maxx = max(num, f[num]);
	for (__int128 i = 1; i <= num; i ++ ) {
		//cout << maxx << '\n';
		maxx = max((dfs(i) % mod) * (dfs(num - i) % mod) % mod, maxx);
	}
	return f[num] = maxx;
//	return f[num] = max((dfs(num >> 1) * dfs((num - (num >> 1))) % mod), max(f[num], num));
}*/
__int128 qpow(__int128 a, __int128 b) {
	if (b == 1) return a;
	if (b == 0) return 1;
    __int128 cnt = qpow(a, b >> 1) % mod;
	if (b % 2 == 0) return cnt * cnt % mod;
	else return (qpow(a, b - 1) % mod) * a % mod;
}
int main() {
	memset(f, -1, sizeof f);
	cin.tie(0);
    for (int i = 1; i <= 2000; i ++ ) {
    	if (i <= 4) {
    		f[i] = i;
    		continue;
		}
		for (int j = 1; j <= (i >> 1); j ++ ) {
			f[i] = max(f[i], (f[j] % mod) * (f[i - j] % mod) % mod);
			f[i] %= mod;
		}
		__int128 x = i % mod;
		f[i] = max(f[i] % mod, x);
	} 
	for (int i = 1; i <= 2000; i ++ ) {
		int num = i, cnt = 0;
		bool fl = 0;
		while (num >= 3) {
			if (num == 4) {
				fl = 1;
				break;
			}
			cnt ++ ;
			num -= 3;
		}
		if (fl) {
			f[i] = max(f[i], (qpow(3, cnt) % mod) * 4 % mod);
		}else {
			f[i] = max(f[i], qpow(3, cnt) % mod);
		}
		f[i] %= mod;
	}
	int T, x;
	cin >> T;
	while (T -- ) {
		cin >> x;
		f[x] %= mod;
		print(f[x]);
		puts("");
	}
	return 0;
}