abc269

\(\textbf{G.}\)

设 \(c _ i = b _ i - a _ i\), \(S _ a = \sum _ {i = 1} ^ {n} a _ i\). 则此时 \(k\) 的答案为选择最少个数的 \(c\) 凑出 \(k - S _ a\) 的答案.

注意到 \(\sum _ {i = 1} ^ {n} c _ i \leq \sum _ {i = 1} ^ {n} b _ i \leq m\). 所以 \(c _ 1, \cdots, c _ n\) 中本质不同的数的个数是 \(\mathcal{O}(\sqrt{m})\) 级别的. 将这些相同的 \(c\) 合并起来变成 \(\mathcal{O}(\sqrt{m})\) 种元素的多重背包. 之后只需二进制拆分重新变成 \(\mathcal{O}(\sqrt{m} \log n)\) 种元素的零一背包.

直接 dp 即可. 时间复杂度 \(\mathcal{O}(n + m \sqrt{m} \log n)\).

void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1), b(n + 1);
	for(int i = 1; i <= n; i ++)
		cin >> a[i] >> b[i];

	int suma = accumulate(a.begin() + 1, a.begin() + n + 1, 0);
	map<int, int> cnt;
	for(int i = 1; i <= n; i ++)
		cnt[b[i] - a[i]] ++;
	vector<pair<int, int>> prod;
	for(auto it : cnt){
		int c = it.first, cntc = it.second;
		for(int dntc = 1; dntc <= cntc; dntc <<= 1){
			prod.emplace_back(dntc * c, dntc), cntc -= dntc;
		}
		prod.emplace_back(cntc * c, cntc);
	}

	vector<int> dp(m + 1, n + 1);
	dp[suma] = 0;
	for(auto [w, v] : prod){
		if(w > 0){
			for(int i = m; i >= w; i --)
				if(dp[i] > dp[i - w] + v)
					dp[i] = dp[i - w] + v;
		}
		if(w < 0){
			for(int i = 0; i <= m + w; i ++)
				if(dp[i] > dp[i - w] + v)
					dp[i] = dp[i - w] + v;
		}
	}
	for(int i = 0; i <= m; i ++)
		cout << (dp[i] == n + 1 ? -1 : dp[i]) << "\n";
}

\(\textbf{H.}\)

设 \(f(u, t)\) 表示在 \(u\) 子树内选择大小为 \(t\) 的反链的方案数.

则 \(f(u, t) = [t = 1] + \sum _ {t _ 1 + \cdots + t _ k = t} f(v _ 1, t _ 1) \cdots f(v _ k, t _ k)\), 其中 \(v _ 1, \cdots, v _ k\) 是 \(u\) 的所有儿子.

设 \(f(u) = \sum _ {t \geq 1} f(u, t) x ^ t\) 是以 \(t\) 为下标的生成函数. 那么 \(f(u) = x + \prod _ {v \in \mathcal{C} _ u} f(v)\).

考虑预处理出 \(u\) 的重儿子 \(h _ u\). 考虑设 \(g(u) = \prod _ {v \in \mathcal{C} _ u - \{ h _ u \}} f(v)\). 那么 \(f(u) = x + g(u) f(h _ u)\).

所以 \(\begin{array}{l} f(u) &= x + g(u) f(h _ u) = x + g(u) (x + g(h _ u) f(h _ {h _ u})) = x(1 + g(u)) + g(u) g(h _ u) f(h _ {h _ u}) \\ &= \cdots = x(1 + g(u) + g(u) g(h _ u) + \cdots) + (x + 1) g(u) g(h _ u) \cdots \end{array}\).

其中依次展开到 \(u\) 的重儿子直到叶子. 我们只在一条重链的顶端计算 \(f(u)\).

考虑快速计算 \(1 + p _ 1 + p _ 1 p _ 2 + \cdots + p _ 1 \cdots p _ k\) 和 \(p _ 1 \cdots p _ k\). 这东西可以通过分治 fft 在 \(\mathcal{O}((\deg p _ 1 + \cdots + \deg p _ k) \log ^ 2 n)\) 内计算.

而显然每个点 \(g(v)\) 显然只会使用恰好 \(1\) 次, 所以每次计算 \(g(v)\) 的时候通过用 huffman树 合并度数 ntt 计算即可. 复杂度为 \(\mathcal{O}((\deg p _ 1 + \cdots + \deg p _ k) \log ^ 2 n)\).

总时间复杂度 \(\mathcal{O}(n \log ^ 3 n)\). 常数很小.

void solve(){
	int n;
	cin >> n;
	vector<int> par(n + 1);
	vector<vector<int>> sons(n + 1);
	for(int i = 2; i <= n; i ++){
		cin >> par[i];
		sons[par[i]].emplace_back(i);
	}

	vector<int> siz(n + 1), h(n + 1);
	for(int i = n; i >= 1; i --){
		siz[i] = 1;
		for(int j : sons[i])
			siz[i] += siz[j];

		for(int j : sons[i])
			if(siz[j] > siz[h[i]])
				h[i] = j;
	}

	struct cmp{
		bool operator ()(const vector<modint> &F, const vector<modint> &G) const {
			return (int)F.size() > (int)G.size();
		}
	} ;
	auto solve = [&](auto solve, const vector<vector<modint>> &polys, int L, int R) -> pair<vector<modint>, vector<modint>> {
		if(L == R)
			return {polys[L], vector<modint>{modint(1)}};
		int M = (L + R) / 2;
		auto [PL, QL] = solve(solve, polys, L, M);
		auto [PR, QR] = solve(solve, polys, M + 1, R);
		return {mul(PL, PR), add(QL, mul(PL, QR))};
	} ;

	vector<vector<modint>> f(n + 1);
	for(int i = n; i >= 1; i --){
		if(h[par[i]] != i){
			vector<vector<modint>> polys;
			for(int j = i; j; j = h[j]){
				priority_queue<vector<modint>, vector<vector<modint>>, cmp> qolys;
				for(int k : sons[j])
					if(k != h[j])
						qolys.emplace(f[k]);
				if(qolys.empty())
					qolys.emplace(vector<modint>{modint(1)});
				while((int)qolys.size() >= 2){
					vector<modint> P = qolys.top(); qolys.pop();
					vector<modint> Q = qolys.top(); qolys.pop();
					qolys.emplace(mul(P, Q));
				}
				polys.emplace_back(qolys.top());
			}
			auto [P, Q] = solve(solve, polys, 0, (int)polys.size() - 1);
			f[i] = add(P, mov(Q, 1));
		}
	}
	for(int k = 1; k <= n; k ++)
		cout << (k < (int)f[1].size() ? f[1][k].val() : 0) << "\n";
}