QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232243#7613. Inverse Problemsinsop90RE 1ms3552kbC++143.5kb2023-10-30 08:30:452023-10-30 08:30:46

Judging History

你现在查看的是最新测评结果

  • [2023-10-30 08:30:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3552kb
  • [2023-10-30 08:30:45]
  • 提交

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

output:


result: