QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232243 | #7613. Inverse Problem | sinsop90 | RE | 1ms | 3552kb | C++14 | 3.5kb | 2023-10-30 08:30:45 | 2023-10-30 08:30:46 |
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
*/
void solve() {
for(int i = 2;i <= 130;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 == 10 && j == 9) 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[0] << " " << '\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: 3552kb
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: -100
Runtime Error
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004