QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276574 | #7613. Inverse Problem | AllTheWayNorth# | ML | 0ms | 4776kb | C++14 | 3.3kb | 2023-12-05 22:59:28 | 2023-12-05 22:59:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int M = 150;
int power(int a, int b) {
long long res = a, ans = 1;
for (; b; b >>= 1, res = res * res % mod) if (b & 1) ans = ans * res % mod;
return ans;
}
struct node {
int n;
vector <int> L[M], R[M];
int f[M];
void build(int N) {
n = N;
f[0] = 1;
for (int i = 1; i <= n - 2; i++) f[i] = 1ll * f[i - 1] * (n - i - 1) % mod;
L[0].push_back(1);
R[0].push_back(1);
int l = 1, r = n - 2;
int suml = 1, sumr = 1;
while (l <= r) {
if (suml < sumr) {
int inv = power(f[l], mod - 2);
for (int i = 0; i + l <= n - 2; i++) {
for (auto j : L[i]) L[i + l].push_back(1ll * j * inv % mod), suml++;
}
l++;
}
else {
for (int i = 0; i + r <= n - 2; i++) {
for (auto j : R[i]) R[i + r].push_back(1ll * j * f[r] % mod), sumr++;
}
r--;
}
}
for (int i = 0; i <= n - 2; i++) {
sort(L[i].begin(), L[i].end());
sort(R[i].begin(), R[i].end());
}
}
int query(int v) {
v = 1ll * v * power(1ll * n * (n - 1) % mod, mod - 2) % mod;
for (int i = 0; i <= n - 2; i++) {
for (auto j : L[i]) {
int cur = 1ll * v * j % mod;
auto ite = lower_bound(R[n - 2 - i].begin(), R[n - 2 - i].end(), cur);
if (ite == R[n - 2 - i].end() || *ite != cur) continue;
printf("%d\n", n);
printf("1 2\n");
int p = 2, tmp = j, rst = i;
for (int t = 1; t <= rst; t++) {
while (rst >= t) {
int nxt = 1ll * tmp * f[t] % mod;
auto ite = lower_bound(L[rst - t].begin(), L[rst - t].end(), nxt);
if (ite == L[rst - t].end() || *ite != nxt) break;
rst -= t, tmp = nxt;
for (int x = 1; x <= t; x++) printf("%d %d\n", p, p + x);
p += t;
}
}
assert(tmp == 1 && rst == 0);
tmp = cur, rst = n - 2 - i;
for (int t = 1; t <= rst; t++) {
while (rst >= t) {
int nxt = 1ll * tmp * power(f[t], mod - 2) % mod;
auto ite = lower_bound(R[rst - t].begin(), R[rst - t].end(), nxt);
if (ite == R[rst - t].end() || *ite != nxt) break;
rst -= t, tmp = nxt;
for (int x = 1; x <= t; x++) printf("%d %d\n", p, p + x);
p += t;
}
}
assert(tmp == 1 && rst == 0);
return 1;
}
}
return 0;
}
} a[M];
void rmain() {
int r;
scanf("%d", &r);
if (r == 1) {
puts("1");
return;
}
for (int i = 2; ; i++) {
if (a[i].n == 0) a[i].build(i);
if (a[i].query(r)) return;
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) rmain();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4776kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 2 2 3 3 4 3 5 1 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
result:
ok OK (4 test cases)
Test #2:
score: -100
Memory Limit Exceeded
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 10 12 12 13 12 14 122 1 2 2 3 3 4 4 5 5 6 6 7 7 8 7 9 9 10 9 11 11 12 11 13 13 14 13 15 13 16 16 17 16 18 16 19 19 20 19 21 19 22 22 23 22 24 22 25 22 26 26 27 26 28 26 29 26 30 30 31 30 32 30 33 30 34 30 35 35 36 35 37 35 38 35 39 35 40 35 41 35 42 42 4...