Home » 国际竞赛 » Details

USACO 2019 December Contest, Platinum Problem 3. Tree Depth

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午3:59

USACO 2019 December Contest, Platinum Problem 3. Tree Depth

For the new year, Farmer John decided to give his cows a festive binary search tree (BST)!

To generate the BST, FJ starts with a permutation $a = {a_{1}, a_{2}, \dots, a_{N}}$ of the integers $1 \dots N$ , where $N \leq 300$ . He then runs the following pseudocode with arguments $1$ and $N .$

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

For example, the permutation ${3, 2, 5, 1, 4}$ generates the following BST:

Let $d_{i} (a)$ denote the depth of node $i$ in the tree corresponding to $a,$ meaning the number of nodes on the path from $a_{i}$ to the root. In the above example, $d_{4} (a) = 1, d_{2} (a) = d_{5} (a) = 2,$ and $d_{1} (a) = d_{3} (a) = 3.$

The number of inversions of $a$ is equal to the number of pairs of integers $(i, j)$ such that $1 \leq i < j \leq N$ and $a_{i} > a_{j} .$ The cows know that the $a$ that FJ will use to generate the BST has exactly $K$ inversions $(0 \leq K \leq \frac{N (N - 1)}{2})$ . Over all $a$ satisfying this condition, compute the remainder when $\sum_{a} d_{i} (a)$ is divided by $M$ for each $1 \leq i \leq N .$

INPUT FORMAT (file treedepth.in):

The only line of input consists of three space-separated integers $N, K,$ and $M$ , followed by a new line. $M$ will be a prime number in the range $[10^{8}, 10^{9} + 9] .$

OUTPUT FORMAT (file treedepth.out):

Print $N$ space-separated integers denoting $\sum_{a} d_{i} (a) (\mod M)$ for each $1 \leq i \leq N .$

BATCHING:

Test cases 3-4 satisfy $N \leq 8.$
Test cases 5-7 satisfy $N \leq 20.$
Test cases 8-10 satisfy $N \leq 50.$

SAMPLE INPUT:

3 0 192603497

SAMPLE OUTPUT:

1 2 3

Here, the only permutation is $a = {1, 2, 3} .$

SAMPLE INPUT:

3 1 144408983

SAMPLE OUTPUT:

3 4 4

Here, the two permutations are $a = {1, 3, 2}$ and $a = {2, 1, 3} .$

Problem credits: Yinzhan Xu

<h3>USACO 2019 December Contest, Platinum Problem 3. Tree Depth 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

For $N \leq 20,$ any reasonable polynomial-time solution should work. One possible approach is to calculate the result for all $n \leq N, k \leq (\binom{n}{2})$ in $O (N^{7}) .$

For additional points, we should find a way to compute $d_{i} (a)$ without explicitly constructing the tree. The key condition is that $j$ is an ancestor of $i$ if $a [j] = min (a [i \dots j]),$ so it follows that

d i (a) = 1 + \sum 1 \leq j < i (a [j] == min (a [j \dots i])) + \sum i < j \leq n (a [j] == min (a [i \dots j])) .

Let's focus on counting the number of permutations $a$ such that $a [j] == min (a [i \dots j])$ for some fixed pair $(i, j)$ satisfying $i < j .$ We'll do this by constructing $a$ one element at a time.

First, we start with a sequence consisting of $a [i]$ only. Then $a [i + 1]$ can be either greater than $a [i]$ or less than $a [i],$ contributing $0$ or $1$ inversion. Then $a [i + 2]$ can take on any of three different values relative to $a [i]$ and $a [i + 1],$ contributing anywhere from $0$ to $2$ inversions. Continuing in this fashion, the possible numbers of inversions in the sub-permutation $a [i \dots j - 1]$ can be represented by the polynomial product

\prod t = 1 j - i (\sum u = 0 t - 1 x u) .

This is known as a generating function because we are encoding a sequence using a polynomial. If we expand it and group together the terms with the same power of $x,$ then a term in the form $c x^{d}$ means that there are exactly $c$ permutations with $d$ inversions.

Adding $a [j]$ contributes $j - i$ inversions regardless of how many inversions $a [i \dots j - 1]$ has. Then we should add the remaining elements of the permutation, each of which can go anywhere in the sorted order. Thus, the final result is given by the generating function

\prod t = 1 n (\sum u = 0 t - 1 x u) \cdot 1 \sum j - i u = 0 x u \cdot x j - i .

The first part of this product does not depend on $i$ or $j,$ and we can calculate it in $O (N^{3})$ time with prefix sums. We can divide it by $\sum_{u = 0}^{j - i} x^{u}$ in $O (N^{2})$ time by reversing the process we used to multiply.

After dividing, all we need is the coefficient of $x^{k - (j - i)} .$ Since the product depends only on $j - i,$ we only need to do $N$ different divisions. Alternatively, we can maintain prefix and suffix products without needing to do division. The process for $i > j$ is almost exactly the same, except $a [j]$ contributes $0$ inversions rather than $i - j .$

The whole solution runs in $O (N^{3})$ time and $O (N^{2})$ memory. My code follows. It turns out that $M$ being prime is irrelevant ...

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
 
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

int MOD;
int n,k;

typedef int T;
struct mi {
	T val; 
	mi() { val = 0; }
	mi(const ll& v) { 
		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
		if (val < 0) val += MOD;
	}
	mi& operator+=(const mi& m) { 
		if ((val += m.val) >= MOD) val -= MOD; 
		return *this; }
	mi& operator-=(const mi& m) { 
		if ((val -= m.val) < 0) val += MOD; 
		return *this; }
};
typedef vector<mi> vmi;
 
void ad(vmi& a, int b) { // multiply by (x^0+x^1+...+x^{b-1})
	a.rsz(sz(a)+b-1);
	R0F(i,sz(a)-b) a[i+b] -= a[i];
	FOR(i,1,sz(a)) a[i] += a[i-1];
}
void sub(vmi& a, int b) {
	ROF(i,1,sz(a)) a[i] -= a[i-1];
	F0R(i,sz(a)-b) a[i+b] += a[i];
	a.rsz(sz(a)-b+1); 
}
mi get(vmi& a, int b) {
	if (b < 0 || b >= sz(a)) return 0;
	return a[b];
}
 
int main() {
	setIO("treedepth"); 
	cin >> n >> k >> MOD;
	vmi v = {1}; FOR(i,1,n+1) ad(v,i);
	vmi ans(n,v[k]);
	FOR(dif,1,n) {
		sub(v,dif+1);
		mi x = get(v,k-dif), y = get(v,k);
		ad(v,dif+1);
		F0R(a,n-dif) {
			ans[a] += x;
			ans[a+dif] += y;
		}
	}
	F0R(i,n) cout << ans[i].val << ' ';
}

[/hide]