QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#177958#6512. Completely Multiplicative Functionmendicillin2#WA 174ms8132kbC++173.6kb2023-09-13 16:30:052023-09-13 16:30:05

Judging History

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

  • [2023-09-13 16:30:05]
  • 评测
  • 测评结果:WA
  • 用时:174ms
  • 内存:8132kb
  • [2023-09-13 16:30:05]
  • 提交

answer

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

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

const int MAXN = 1.1e6;
vi ps;
int pri[MAXN];

const int L = 60;
vector<int> prec[L+1][L+1];

void precomp() {
	fill(pri + 2, pri + MAXN, 0);
	for (int a = 2; a * a < MAXN; a++) {
		if (pri[a]) continue;
		for (int b = 2*a; b < MAXN; b += a) {
			if (!pri[b]) pri[b] = a;
		}
	}
	for (int a = 2; a < MAXN; a++) {
		if (pri[a] == 0) ps.push_back(a);
	}

	prec[1][1] = {1, 1};
	for (int n = 2; n <= L; n++) {
		vector<int> cur_ps;
		for (int p : ps) {
			if (p <= n) {
				cur_ps.push_back(p);
			} else {
				break;
			}
		}
		int num = int(cur_ps.size());
		//cerr << "num=" << num << endl;
		for (int m = 0; m < (1 << num); m++) {
			vector<int> f(n+1, 0);
			f[1] = 1;
			for (int i = 0; i < num; i++) {
				int p = cur_ps[i];
				if (m & (1 << i)) {
					f[p] = 1;
				} else {
					f[p] = -1;
				}
			}
			int cur_k = 0;
			for (int a = 1; a <= n; a++) {
				if (f[a] == 0) {
					assert(pri[a] != 0);
					f[a] = f[a / pri[a]] * f[pri[a]];
					assert(abs(f[a]) == 1);
				}
				cur_k += f[a];
			}
			assert(abs(cur_k) <= n);
			if (cur_k >= 0) {
				prec[n][cur_k] = f;
			}
		}
	}
}

vector<int> solve(int N, int K) {
	if (N <= L) return prec[N][K];

	if ((N-K) % 2) return {};

	int need = (N-K) / 2;
	vector<int> res(N+1, 1);
	{
		for (int p : ps) {
			if (ll(p) * p <= N) continue;
			if (p > N) break;
			int c = N/p;
			if (c <= need) {
				for (int a = p; a <= N; a += p) {
					res[a] = -1;
				}
				need -= c;
			}
		}
	}
	if (need > 0) {
		for (int mask = 0; mask < (1 << 4); mask++) {
			need = (N-K)/2;
			res.assign(N+1, 1);
			// 2, 3, 5, 7
			for (int i = 0; i < 4; i++) {
				if (mask & (1 << i)) {
					res[ps[i]] = -1;
					for (int a = ps[i]; a <= N; a += ps[i]) {
						if (a % (ps[i] * ps[i]) != 0) {
							res[a] *= -1;
						}
					}
				}
			}
			for (int a = 1; a <= N; a++) {
				if (res[a] == -1) need--;
			}
			if (need < 0) continue;
			for (int p : ps) {
				if (ll(p) * p <= N) continue;
				if (p > N) break;
				int c = 0;
				for (int a = p; a <= N; a += p) {
					if (res[a] == 1) {
						c += 1;
					} else {
						c -= 1;
					}
				}
				//cerr << "p = " << p << ", c = " << c << endl;
				if (c >= 0 && c <= need) {
					need -= c;
					for (int a = p; a <= N; a += p) {
						res[a] = -res[a];
					}
				}
			}
			if (need == 0) break;
		}
	}
	assert(need == 0);
	return res;
}

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rand_int(int a, int b) {
	return uniform_int_distribution<int>(a, b)(mt);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	precomp();

	const bool debug = false;

	//exit(0);

	int T;
	if (!debug) {
		cin >> T;
	} else {
		T = 10000;
	}
	while (T--) {
		int N, K;
		if (!debug) {
			cin >> N >> K;
		} else {
			N = rand_int(200, 1000);
			K = rand_int(0, 10);
		}
		auto res = solve(N, K);
		if (res.empty()) {
			cout << -1 << '\n';
		} else {
			//assert(int(res.size()) == N+1);
			assert(accumulate(res.begin() + 1, res.end(), 0) == K);
			for (int i = 1; i <= N; i++) {
				//assert(abs(res[i]) == 1);
				cout << res[i] << " \n"[i==N];
			}
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 151ms
memory: 8132kb

input:

4
4 2
10 0
10 1
10 10

output:

1 -1 1 1
1 -1 1 1 1 -1 -1 -1 1 -1
-1
1 1 1 1 1 1 1 1 1 1

result:

ok ok (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 174ms
memory: 8108kb

input:

11475
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11...

output:

-1
1
1 -1
-1
1 1
-1
1 -1 1
-1
1 1 1
1 -1 -1 1
-1
1 -1 1 1
-1
1 1 1 1
-1
1 -1 -1 1 1
-1
1 -1 1 1 1
-1
1 1 1 1 1
1 -1 1 1 -1 -1
-1
1 -1 1 1 1 -1
-1
1 1 1 1 -1 1
-1
1 1 1 1 1 1
-1
1 -1 1 1 -1 -1 1
-1
1 -1 1 1 1 -1 1
-1
1 1 1 1 -1 1 1
-1
1 1 1 1 1 1 1
1 -1 1 1 -1 -1 1 -1
-1
1 -1 1 1 1 -1 1 -1
-1
1 1 -1 ...

result:

wrong answer f[6] != f[2] * f[3] (test case 1892)