Problem – E – Codeforces

题意：有一个指定大小的区域，现在需要在这个区域里放一些照片，每张照片之间和最外面一圈都必须有一个宽为 $1$ 的边框。

照片可以进行放缩，只要长宽比不变即可。输入是递归给出的，一个子区域可以是单张照片，也可以横向或竖向划分成若干个更小的区域。

判断是否有解，如果有解则输出方案。坐标范围 $10^3$，子区域和照片的个数加起来不超过 $2\times 10^3$。

考虑把每个子区域或者照片的长和宽分别设为一个未知量，那么照片的长和宽成比例是一个等式，子区域划分的一维长度加起来等于区间长度是一个等式，没有划分的一维依次相等也是一个等式。

假设总共有 $n$ 个子区域或者照片，那么就得到了有 $2n$ 个未知量和 $2n – 1$ 个等式的方程组。再加上总体的宽度固定这一个等式，就得到了一个 $2n \times 2n$ 的满秩（显然）方程组。

如果能解出这个方程组，判断一下总体的高度是否和给定的恰好相符，并且每个未知量的值都是整数，就说明是有解的，否则无解。

解稀疏方程组有一种方法是用 Berlekamp-Massey 求最小递推式，不过因为它的精度很差，可以在模意义下做。显然方程组中非零系数只有 $O(n)$ 个，所以复杂度是 $O(n^2)$。（Berlekamp-Massey 的各种用法属实有点牛逼，我在考虑要不要单发一篇这个算法的应用。）

注意瓶颈都在模意义乘法上，所以大部分运算都是 $64$ 位整数运算，所以才会有在 CF 上交 $64$ 位能过，而 $32$ 位刚好过不了的情况。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 4005, p = 1004535809;

int qpow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1)
			ans = (long long)ans * a % p;
		
		b >>= 1;
		a = (long long)a * a % p;
	}
	return ans;
}

vector<int> berlekamp_massey(const vector<int> &a) {
	vector<int> v, last; // v is the answer, 0-based
	int k = -1, delta = 0;

	for (int i = 0; i < (int)a.size(); i++) {

		int tmp = 0;
		for (int j = 0; j < (int)v.size(); j++)
			tmp = (tmp + (long long)a[i - j - 1] * v[j]) % p;
		
		if (a[i] == tmp)
			continue;
		
		if (k < 0) {
			k = i;
			delta = (a[i] - tmp + p) % p;
			v = vector<int>(i + 1);

			continue;
		}

		vector<int> u = v;
		int val = (long long)(a[i] - tmp + p) * qpow(delta, p - 2) % p;

		if (v.size() < last.size() + i - k)
			v.resize(last.size() + i - k);
		
		(v[i - k - 1] += val) %= p;
		
		for (int j = 0; j < (int)last.size(); j++) {
			v[i - k + j] = (v[i - k + j] - (long long)val * last[j]) % p;
			if (v[i - k + j] < 0)
				v[i - k + j] += p;
		}

		if ((int)u.size() - i < (int)last.size() - k) {
			last = u;
			k = i;
			delta = a[i] - tmp;
			if (delta < 0)
				delta += p;
		}
	}

	for (auto &x : v) // 一般是需要最小递推式的, 所以处理一下
		x = (p - x) % p;
	v.insert(v.begin(), 1);

	return v; // $\forall i, \sum_{j = 0} ^ m a_{i - j} v_j = 0$
}

vector<int> solve_sparse_equations(const vector<tuple<int, int, int> > &A, const vector<int> &b) {
	int n = (int)b.size(); // 0-based

	vector<vector<int> > f({b});

	for (int i = 1; i < 2 * n; i++) {
		vector<int> v(n);
		auto &u = f.back();

		for (auto [x, y, z] : A)// [x, y, value]
			v[x] = (v[x] + (long long)u[y] * z) % p;

		f.push_back(v);
	}

	vector<int> w(n);
	mt19937 gen;
	for (auto &x : w)
		x = gen() % (p - 1) + 1;

	vector<int> a(2 * n);
	for (int i = 0; i < 2 * n; i++)
		for (int j = 0; j < n; j++)
			a[i] = (a[i] + (long long)f[i][j] * w[j]) % p;
	
	auto c = berlekamp_massey(a);
	int m = (int)c.size();

	vector<int> ans(n);

	for (int i = 0; i < m - 1; i++)
		for (int j = 0; j < n; j++)
			ans[j] = (ans[j] + (long long)c[m - 2 - i] * f[i][j]) % p;

	int inv = qpow(p - c[m - 1], p - 2);

	for (int i = 0; i < n; i++)
		ans[i] = (long long)ans[i] * inv % p;

	return ans;
}

vector<int> ch[maxn];

int tp[maxn], hor[maxn], ver[maxn]; // 0: horizonal  1: vertical  -1 : photo
int cnt;

char a[1005][1005];

int build(int t) {
	int k;
	scanf("%d", &k);

	int o = ++cnt;

	if (!k) {
		scanf("%d%d", &hor[o], &ver[o]);
		tp[o] = -1;
	}
	else {
		tp[o] = t;
		while (k--)
			ch[o].push_back(build(t ^ 1));
	}

	return o;
}

void dfs(int o, int lx, int ly, int rx, int ry) { // x is vertical
	for (int i = ly; i <= ry; i++)
		a[lx][i] = a[rx][i] = '*';
	
	for (int i = lx + 1; i < rx; i++)
		a[i][ly] = a[i][ry] = '*';
	
	if (tp[o] == 0) {
		int y = ly;
		for (int u : ch[o]) {
			dfs(u, lx, y, rx, y + hor[u] + 1);
			y += hor[u] + 1;
		}
	}
	else if (tp[o] == 1) {
		int x = lx;
		for (int u : ch[o]) {
			dfs(u, x, ly, x + ver[u] + 1, ry);
			x += ver[u] + 1;
		}
	}
}

int main() {

	int H, V;
	scanf("%d%d", &H, &V);

	build(0);

	int n = cnt; // 2n variables

	if (H <= 2 || V <= 2) {
		printf("Impossible\n");
		return 0;
	}

	int id = 0;

	vector<tuple<int, int, int> > A;
	vector<int> b;
	
	for (int i = 1; i <= n; i++) {
		if (tp[i] == -1) {
			A.emplace_back(id, i - 1, ver[i]);
			A.emplace_back(id, i + n - 1, p - hor[i]);
			b.push_back(0);
			id++;
		}
		else if (tp[i] == 0) {
			for (int x : ch[i]) {
				A.emplace_back(id, i + n - 1, 1);
				A.emplace_back(id, x + n - 1, p - 1);
				b.push_back(0);
				id++;
			}

			A.emplace_back(id, i - 1, 1);
			for (int x : ch[i])
				A.emplace_back(id, x - 1, p - 1);
			b.push_back((int)ch[i].size() - 1);
			id++;
		}
		else {
			for (int x : ch[i]) {
				A.emplace_back(id, i - 1, 1);
				A.emplace_back(id, x - 1, p - 1);
				b.push_back(0);
				id++;
			}

			A.emplace_back(id, i + n - 1, 1);
			for (int x : ch[i])
				A.emplace_back(id, x + n - 1, p - 1);
			b.push_back((int)ch[i].size() - 1);
			id++;
		}
	}

	A.emplace_back(id, 0, 1);
	b.push_back(H - 2);
	
	assert(++id == n * 2);

	auto x = solve_sparse_equations(A, b);

	bool bad = false;

	for (int i = 1; i <= n; i++) {
		hor[i] = x[i - 1];
		ver[i] = x[i + n - 1];

		if (hor[i] > H || ver[i] > V || !hor[i] || !ver[i])
			bad = true;
	}
	
	bad |= (ver[1] != V - 2);

	if (bad)
		printf("Impossible\n");
	else {
		dfs(1, 1, 1, V, H);

		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= H; j++)
				putchar(a[i][j] ? '*' : ' ');
			
			putchar('\n');
		}
	}

	return 0;
}