QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224921#7613. Inverse Problemucup-team1209TL 0ms7772kbC++203.1kb2023-10-23 17:47:482023-10-23 17:47:49

Judging History

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

  • [2023-10-23 17:47:49]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7772kb
  • [2023-10-23 17:47:48]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;

const int N = 300;
const int mod = 1e9 + 7;
using u64 = unsigned long long;
int fac[N], inv[N], ifac[N];
int r[N];
std::vector<int> ans[N];

void output(std::vector<int> deg) {
	cout << deg.size() << '\n';
	for(int i = 1;i <= deg.size();++i) {
		for(int j = 0;j < deg.size();++j) if(deg[j] == 1) {
			-- deg[j];
			int k = max_element(deg.begin(), deg.end()) - deg.begin();
			--deg[k];
			cout << j + 1 << ' ' << k + 1 << '\n';
		}
	}
}
struct bag {
	std::vector<int> dp[N][N];
	void clear(int n) {
		for(int i = 0;i <= n;++i)
			for(int j = 0;j <= n + n - 2;++j)
				dp[i][j].clear();
	}
	void ins(int x, int n, int * f) {
		for(int i = 0;i < n;++i) {
			for(int j = 0;j + x + (n - i - 1) <= n + n - 2;++j) {
				for(int w : dp[i][j]) {
					dp[i + 1][j + x].push_back((u64) w * f[n - 1 - x] % mod);
				}
			}
		}
	}
	void push(int l, int r, int cnt, int deg, int * f, int w, auto & d, int n) {
		for(int s = l;cnt && s <= r;s += 2) {
			for(;s <= deg && cnt;) {
				auto & v = dp[cnt - 1][deg - s];
				int nxt = (u64) w * f[n - 1 - s] % mod;
				auto it = std::ranges::find(v, nxt);
				if(it == v.end()) break;
				d.push_back(s);
				w = nxt;
				cnt -= 1;
				deg -= s;
			}
		}
	}
} a[2];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
	for(int i = 2;i < N;++i) {
		inv[i] = u64(mod - mod / i) * inv[mod % i] % mod;
		fac[i] = (u64) fac[i - 1] * i % mod;
		ifac[i] = (u64) ifac[i - 1] * inv[i] % mod;
	}
	int t; cin >> t;
	for(int i = 0;i < t;++i) {
		cin >> r[i];
		if(r[i] == 1) {
			ans[i] = {0};
		}
	}
	for(int n = 2;;++n) {
		a[0].dp[0][0] = {1};
		a[1].dp[0][0] = {1};
		for(int i = 1;i < n;i += 2) {
			a[0].ins(i, n, ifac);
		}
		for(int i = 2;i < n;i += 2) {
			a[1].ins(i, n, fac);
		}
		int ssize = 0;
		int ssize1 = 0;
		u64 su = 0;
		u64 val = (u64) inv[n] * inv[n - 1] % mod;
		for(int i = 0;i < n;++i) {
			val = val * ifac[n - 2] % mod;
		}
		for(int i = 0;i <= n;++i) {
			for(int k = 0;k < t;++k) {
				if(ans[k].size()) continue;
				for(int j = 0;j <= n + n - 2;++j) {
					auto & v = a[0].dp[n - i][n + n - 2 - j];
					if(!v.size()) continue;
					if(!a[1].dp[i][j].size()) continue;
					std::ranges::sort(v);
					u64 z = val * r[k] % mod;
					su += a[0].dp[i][j].size() * v.size();
					ssize += a[1].dp[i][j].size();
					ssize1 += v.size();
					for(int w : a[1].dp[i][j]) {
						u64 p = z * w % mod;
						auto it = std::ranges::lower_bound(v, p);
						if(it == v.end() || *it != p) continue;

						a[0].push(1, n - 1, n - i, n + n - 2 - j, fac, p, ans[k], n);
						a[1].push(2, n - 1, i, j, ifac, w, ans[k], n);
//						std::cerr << "done " << '\n';
						break;
					}
					if(ans[k].size()) break;
				}
			}
		}
//		std::cerr << n << ' ' << ssize << ' ' << ssize1 << ' ' << su << std::endl;
		a[0].clear(n);
		a[1].clear(n);
		int done = 1;
		for(int i = 0;i < t;++i) {
			done = done && ans[i].size();
		}
		if(done) {
			break;
		}
	}
	for(int i = 0;i < t;++i) {
		output(ans[i]);
	}

}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7772kb

input:

4
2
360
1
509949433

output:

2
1 2
5
1 4
2 4
3 5
4 5
1
10
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 10

result:

ok OK (4 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

9
185396120
468170792
837583517
696626231
338497514
762842660
800028852
928391161
733524004

output:


result: