QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232254 | #7613. Inverse Problem | sinsop90 | AC ✓ | 38251ms | 13940kb | C++14 | 3.5kb | 2023-10-30 08:48:25 | 2023-10-30 08:48:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, blc = 5;
int a[155], gfac[155], ifac[155], fac[155], n, flag, ID, NOW, IFAC[155];
vector<pair<int, int>> ASK;
vector<int> L, R, res[15];
int ksm(int p, int q) {
int ress = 1;
while(q) {
if(q & 1) ress = 1ll * ress * p % mod;
p = 1ll * p * p % mod;
q >>= 1;
}
return ress;
}
void dfsL(int ress, int las, int now, int dep) {
// cout << ress << " " << las << " " << now << " " << dep << '\n';
if(!ress) {
if(!flag) {
// cout << "!!!!!!!" << '\n';
L.push_back(now);
return;
}
else {
if(now != flag) return;
for(int i = 1;i < dep;i++) res[ID].push_back(a[i]);
}
return;
}
for(int i = min(ress, las);i >= 1;i--) {
// cout << i << " " << gfac[i] << '\n';
a[dep] = i;
dfsL(ress - i, i, 1ll * now * gfac[i + 1] % mod * IFAC[NOW - 2] % mod, dep + 1);
}
}
void dfsR(int ress, int las, int now, int dep) {
if(!ress) {
if(!flag) {
R.push_back(now);
return;
}
else {
if(now != flag) return;
for(int i = 1;i < dep;i++) res[ID].push_back(a[i]);
}
return;
}
for(int i = las;i <= ress;i++) {
a[dep] = i;
dfsR(ress - i, i, 1ll * now * ifac[i + 1] % mod * fac[NOW - 2] % mod , dep + 1);
}
}
/*
4
2
360
1
509949433
1
269199917
*/
void solve() {
for(int i = 2;i <= 125;i++) {
NOW = i;
int inv = ksm(i * (i - 1), mod - 2);
// cout << i << " " << inv << '\n';
gfac[i - 1] = 1;
for(int du = i - 2;du >= 0;du--) gfac[du] = 1ll * gfac[du + 1] * (i - 1 - du) % mod;
// cout << gfac[1] << '\n';
for(int du = 0;du <= i - 1;du++) ifac[du] = ksm(gfac[du], mod - 2);
for(int j = 0;j <= i - 2;j++) {
L.clear(), R.clear();
// if(i == 55 && j == 0) cout << "!!!!" << " " << inv << '\n';
dfsL(j, blc, 1, 1);
dfsR(i - 2 - j, blc + 1, 1, 1);
sort(L.begin(), L.end()), sort(R.begin(), R.end());
// cout << L.size() << " " << R.size() << "!!!!!" << '\n';
// cout << i << " " << j << " " << L.size() << " " << R.size() << '\n';
for(int _ = 0;_ < ASK.size();_ ++) {
pair<int, int> T = ASK[_];
for(int X : L) {
int Y = 1ll * T.first * inv % mod * X % mod;
int pos = lower_bound(R.begin(), R.end(), Y) - R.begin();
// cout << i << " " << j << " " << X << " " << Y << " " << pos << " " << R.size() << " " << T.second << '\n';
if(pos == R.size()) continue;
if(R[pos] != Y) continue;
// cout << "!!" << endl;
ID = T.second;
flag = X;
dfsL(j, blc, 1, 1);
flag = Y;
dfsR(i - 2 - j, blc + 1, 1, 1);
flag = 0;
while(res[ID].size() < i) res[ID].push_back(0);
swap(ASK[_], ASK.back()), ASK.pop_back();
_ --;
break;
}
}
if(!ASK.size()) return;
// cout << i << " " << j << " " << ASK.size() << '\n';
}
// cout << i << " " << ASK.size() <<'\n';
}
}
void check() {
for(int i = 1;i <= n;i++) {
cout << res[i].size() << '\n';
res[i][0] ++;
// for(int X : res[i]) cout << X << "\n";
int L = 1;
for(int j = 0;j < res[i].size();j++) {
for(int k = L;k <= L + res[i][j] - 1;k++) cout << j + 1 << " " << k + 1 << '\n';
L = L + res[i][j];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
fac[0] = 1;
for(int i = 1;i <= 130;i++) fac[i] = 1ll * fac[i - 1] * i % mod;
for(int i = 1;i <= 130;i++) IFAC[i] = ksm(fac[i], mod - 2);
for(int i = 1, x;i <= n;i++) {
cin >> x;
if(x == 1) res[i].push_back(-1);
else ASK.push_back({x, i});
}
solve();
check();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3372kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 2 1 3 1 4 2 5 1 10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
result:
ok OK (4 test cases)
Test #2:
score: 0
Accepted
time: 33866ms
memory: 13940kb
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 122 1 2 1 3 1 4 1 5 1 6 1 7 2 8 2 9 2 10 2 11 3 12 3 13 3 14 3 15 4 16 4 17 4 18 5 19 5 20 5 21 6 22 6 23 6 24 7 25 7 26 8 27 8 28 9 29 9 30 10 31 11 32 12 33 13 34 14 35 15 36 15 37 15 38 15 39 15 40 15 41 15 42 16 43 16 44 16 45 16 46 16...
result:
ok OK (9 test cases)
Test #3:
score: 0
Accepted
time: 38251ms
memory: 13540kb
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230
output:
124 1 2 1 3 1 4 1 5 1 6 1 7 2 8 2 9 2 10 3 11 3 12 4 13 5 14 6 15 7 16 8 17 9 18 10 19 11 20 12 21 13 22 14 23 14 24 14 25 14 26 14 27 14 28 15 29 15 30 15 31 15 32 15 33 15 34 15 35 16 36 16 37 16 38 16 39 16 40 16 41 16 42 17 43 17 44 17 45 17 46 17 47 17 48 17 49 18 50 18 51 18 52 18 53 18 54 18 ...
result:
ok OK (10 test cases)
Test #4:
score: 0
Accepted
time: 7652ms
memory: 4408kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 1 2 102 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 7 14 8 15 9 16 9 17 9 18 9 19 9 20 9 21 10 22 10 23 10 24 10 25 10 26 10 27 10 28 10 29 11 30 11 31 11 32 11 33 11 34 11 35 11 36 11 37 11 38 12 39 12 40 12 41 12 42 12 43 12 44 12 45 12 46 12 47 12 48 13 49 13 50 13 51 13 52 13 53 13 5...
result:
ok OK (10 test cases)
Test #5:
score: 0
Accepted
time: 2604ms
memory: 3884kb
input:
10 269199917 392009324 753889928 751355133 472639410 132096559 331333826 40414701 72847302 475706026
output:
55 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 84 1 2 1 3 1 4 1 5 1 6 2 7 2 8 2 9 ...
result:
ok OK (10 test cases)
Extra Test:
score: 0
Extra Test Passed