QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225444#7613. Inverse Problemucup-team1209Compile Error//C++203.2kb2023-10-24 17:34:232023-10-24 17:34:25

Judging History

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

  • [2023-10-24 17:34:25]
  • 评测
  • [2023-10-24 17:34:23]
  • 提交

answer

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

const int N = 300;
const int mod = 1e9 + 7;
std::bitset<mod> vis;
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 += 1) {
			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};
		int lim = std::max(n / 18, 1);
		for(int i = 1;i <= lim;i += 1) {
			a[0].ins(i, n, ifac);
		}
		for(int i = lim + 1;i < n;i += 1) {
			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 x : v) vis.set(p);
					for(int w : a[1].dp[i][j]) {
						u64 p = z * w % mod;
						if(!vis.test(p)) continue;

						a[0].push(1, lim, n - i, n + n - 2 - j, fac, p, ans[k], n);
						a[1].push(lim + 1, n - 1, i, j, ifac, w, ans[k], n);
//						std::cerr << "done " << '\n';
						break;
					}
					for(int x : v) vis.reset(p);
					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]);
	}

}

詳細信息

answer.code: In function ‘int main()’:
answer.code:98:64: error: ‘p’ was not declared in this scope
   98 |                                         for(int x : v) vis.set(p);
      |                                                                ^
answer.code:108:66: error: ‘p’ was not declared in this scope
  108 |                                         for(int x : v) vis.reset(p);
      |                                                                  ^