QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232254#7613. Inverse Problemsinsop90AC ✓38251ms13940kbC++143.5kb2023-10-30 08:48:252023-10-30 08:48:26

Judging History

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

  • [2023-10-30 08:48:26]
  • 评测
  • 测评结果:AC
  • 用时:38251ms
  • 内存:13940kb
  • [2023-10-30 08:48:25]
  • 提交

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