QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177958 | #6512. Completely Multiplicative Function | mendicillin2# | WA | 174ms | 8132kb | C++17 | 3.6kb | 2023-09-13 16:30:05 | 2023-09-13 16:30:05 |
Judging History
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)