QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#322648 | #8215. Isomorphic Delight | triple__a# | WA | 1ms | 3996kb | C++20 | 10.3kb | 2024-02-07 13:53:55 | 2024-02-07 13:53:56 |
Judging History
answer
// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define int long long
#define i128 __int128_t
using namespace std;
constexpr int P = 998244353;
// constexpr int P = 1e9+7;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x%P)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Z &a) {
i64 v;
is >> v;
a = Z(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Z &a) {
return os << a.val();
}
};
std::vector<int> rev;
std::vector<Z> roots{0, 1};
void dft(std::vector<Z> &a) {
int n = a.size();
if ((int)(rev.size()) != n) {
int k = __builtin_ctz(n) - 1;
rev.resize(n);
for (int i = 0; i < n; i++) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
}
}
for (int i = 0; i < n; i++) {
if (rev[i] < i) {
std::swap(a[i], a[rev[i]]);
}
}
if ((int)(roots.size()) < n) {
int k = __builtin_ctz(roots.size());
roots.resize(n);
while ((1 << k) < n) {
Z e = power(Z(3), (P - 1) >> (k + 1));
for (int i = 1 << (k - 1); i < (1 << k); i++) {
roots[2 * i] = roots[i];
roots[2 * i + 1] = roots[i] * e;
}
k++;
}
}
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
Z u = a[i + j];
Z v = a[i + j + k] * roots[k + j];
a[i + j] = u + v;
a[i + j + k] = u - v;
}
}
}
}
void idft(std::vector<Z> &a) {
int n = a.size();
std::reverse(a.begin() + 1, a.end());
dft(a);
Z inv = (1 - P) / n;
for (int i = 0; i < n; i++) {
a[i] *= inv;
}
}
struct Poly {
std::vector<Z> a;
Poly() {}
explicit Poly(int size, std::function<Z(int)> f = [](int) { return 0; }) : a(size) {
for (int i = 0; i < size; i++) {
a[i] = f(i);
}
}
Poly(const std::vector<Z> &a) : a(a) {}
Poly(const std::initializer_list<Z> &a) : a(a) {}
int size() const {
return a.size();
}
void resize(int n) {
a.resize(n);
}
Z operator[](int idx) const {
if (idx < size()) {
return a[idx];
} else {
return 0;
}
}
Z &operator[](int idx) {
return a[idx];
}
Poly mulxk(int k) const {
auto b = a;
b.insert(b.begin(), k, 0);
return Poly(b);
}
Poly modxk(int k) const {
k = std::min(k, size());
return Poly(std::vector<Z>(a.begin(), a.begin() + k));
}
Poly divxk(int k) const {
if (size() <= k) {
return Poly();
}
return Poly(std::vector<Z>(a.begin() + k, a.end()));
}
friend Poly operator+(const Poly &a, const Poly &b) {
std::vector<Z> res(std::max(a.size(), b.size()));
for (int i = 0; i < (int)(res.size()); i++) {
res[i] = a[i] + b[i];
}
return Poly(res);
}
friend Poly operator-(const Poly &a, const Poly &b) {
std::vector<Z> res(std::max(a.size(), b.size()));
for (int i = 0; i < (int)(res.size()); i++) {
res[i] = a[i] - b[i];
}
return Poly(res);
}
friend Poly operator-(const Poly &a) {
std::vector<Z> res(a.size());
for (int i = 0; i < (int)(res.size()); i++) {
res[i] = -a[i];
}
return Poly(res);
}
friend Poly operator*(Poly a, Poly b) {
if (a.size() == 0 || b.size() == 0) {
return Poly();
}
if (a.size() < b.size()) {
std::swap(a, b);
}
if (b.size() < 128) {
Poly c(a.size() + b.size() - 1);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
c[i + j] += a[i] * b[j];
}
}
return c;
}
int sz = 1, tot = a.size() + b.size() - 1;
while (sz < tot) {
sz *= 2;
}
a.a.resize(sz);
b.a.resize(sz);
dft(a.a);
dft(b.a);
for (int i = 0; i < sz; ++i) {
a.a[i] = a[i] * b[i];
}
idft(a.a);
a.resize(tot);
return a;
}
friend Poly operator*(Z a, Poly b) {
for (int i = 0; i < (int)(b.size()); i++) {
b[i] *= a;
}
return b;
}
friend Poly operator*(Poly a, Z b) {
for (int i = 0; i < (int)(a.size()); i++) {
a[i] *= b;
}
return a;
}
Poly &operator+=(Poly b) {
return (*this) = (*this) + b;
}
Poly &operator-=(Poly b) {
return (*this) = (*this) - b;
}
Poly &operator*=(Poly b) {
return (*this) = (*this) * b;
}
Poly deriv() const {
if (a.empty()) {
return Poly();
}
std::vector<Z> res(size() - 1);
for (int i = 0; i < size() - 1; ++i) {
res[i] = (i + 1) * a[i + 1];
}
return Poly(res);
}
Poly integr() const {
std::vector<Z> res(size() + 1);
for (int i = 0; i < size(); ++i) {
res[i + 1] = a[i] / (i + 1);
}
return Poly(res);
}
Poly inv(int m) const {
Poly x{a[0].inv()};
int k = 1;
while (k < m) {
k *= 2;
x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
}
return x.modxk(m);
}
Poly log(int m) const {
return (deriv() * inv(m)).integr().modxk(m);
}
Poly exp(int m) const {
Poly x{1};
int k = 1;
while (k < m) {
k *= 2;
x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
}
return x.modxk(m);
}
Poly pow(int k, int m) const {
int i = 0;
while (i < size() && a[i].val() == 0) {
i++;
}
if (i == size() || 1LL * i * k >= m) {
return Poly(std::vector<Z>(m));
}
Z v = a[i];
auto f = divxk(i) * v.inv();
return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
}
Poly sqrt(int m) const {
Poly x{1};
int k = 1;
while (k < m) {
k *= 2;
x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((P + 1) / 2);
}
return x.modxk(m);
}
Poly mulT(Poly b) const {
if (b.size() == 0) {
return Poly();
}
int n = b.size();
std::reverse(b.a.begin(), b.a.end());
return ((*this) * b).divxk(n - 1);
}
std::vector<Z> eval(std::vector<Z> x) const {
if (size() == 0) {
return std::vector<Z>(x.size(), 0);
}
const int n = std::max((int)(x.size()), size());
std::vector<Poly> q(4 * n);
std::vector<Z> ans(x.size());
x.resize(n);
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
q[p] = Poly{1, -x[l]};
} else {
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
q[p] = q[2 * p] * q[2 * p + 1];
}
};
build(1, 0, n);
std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) {
if (r - l == 1) {
if (l < (int)(ans.size())) {
ans[l] = num[0];
}
} else {
int m = (l + r) / 2;
work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l));
work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m));
}
};
work(1, 0, n, mulT(q[1].inv(n)));
return ans;
}
};
const int N=500007;
const int INF=LLONG_MAX/4;
mt19937 rng(1234);
int n;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n;
if (n==1){cout<<"YES\n0\n"; return 0;}
if (n<=5){cout<<"NO\n"; return 0;}
if (n<=6){cout<<"YES\n6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n"; return 0;}
cout<<"YES\n";
vector<int> lst;
lst.push_back(1);
for (int i=7;i<=5000;++i) lst.push_back(i);
int sum=0, cur=0;
while (1){
if (sum>n) break;
sum+=lst[cur], cur++;
}
vector<pair<int,int>> ans;
auto ou=[&](int mx,int n){
// cerr<<"cerr: "<<mx<<" "<<n<<endl;
if (n==1) return;
for (int i=1;i+1<n;++i) ans.push_back({mx-i+1,mx-i});
ans.push_back({mx-2,mx-n+1});
};
// cerr<<cur<<endl;
for (int i=0;i+2<cur;++i){
ou(n,lst[i]), n-=lst[i];
}
ou(n,n);
cout<<ans.size()<<"\n";
for (auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6
output:
YES 6 1 2 2 3 1 3 3 4 2 5 5 6
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
7
output:
YES 6 7 6 6 5 5 4 4 3 3 2 5 1
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
8
output:
YES 6 7 6 6 5 5 4 4 3 3 2 5 1
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
9
output:
YES 7 8 7 7 6 6 5 5 4 4 3 3 2 6 1
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
10
output:
YES 8 9 8 8 7 7 6 6 5 5 4 4 3 3 2 7 1
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
11
output:
YES 9 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 8 1
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
12
output:
YES 10 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 9 1
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
13
output:
YES 11 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 10 1
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
14
output:
YES 12 13 12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 11 1
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
15
output:
YES 13 14 13 13 12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 12 1
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
16
output:
YES 13 15 14 14 13 13 12 12 11 11 10 13 9 8 7 7 6 6 5 5 4 4 3 3 2 6 1
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
17
output:
YES 14 16 15 15 14 14 13 13 12 12 11 14 10 9 8 8 7 7 6 6 5 5 4 4 3 3 2 7 1
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
18
output:
YES 15 17 16 16 15 15 14 14 13 13 12 15 11 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 8 1
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
19
output:
YES 16 18 17 17 16 16 15 15 14 14 13 16 12 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 9 1
result:
ok Everything ok
Test #20:
score: -100
Wrong Answer
time: 1ms
memory: 3996kb
input:
598
output:
YES 569 597 596 596 595 595 594 594 593 593 592 595 591 590 589 589 588 588 587 587 586 586 585 585 584 588 583 582 581 581 580 580 579 579 578 578 577 577 576 576 575 580 574 573 572 572 571 571 570 570 569 569 568 568 567 567 566 566 565 571 564 563 562 562 561 561 560 560 559 559 558 558 557 557 ...
result:
wrong answer contestant's solution is worse (more edges) than jury's