Codeforces Round #745 (Div. 2) Mathematics Curriculum 题解 (Java/C++)

题解

首先我们先不考虑good number的数目要恰好等于k这个条件，我们先考虑good number本身的性质。

不难发现，无论如何n一定在最大值中。
这样一来，很自然的，如果m=1，那么这个x是且只能是n。
更进一步，m=1时，当且仅当k=1有解，且解为n!。否则一定没有解。

现在我们来考虑m=2的情况。不难想到n-1一定是一个good number，但是是否其他的数可能成为good number呢？
比如n-5是一个good number，我们可以给出下面这种构造[?,...,?, n-5, ?,...,?, n , n-1, n-2,n-3,n-4]。此时n-5也是一个good number。
但我们仔细考量n-5能成为good number的原因后我们发现，其实n右边的所有的值都和n-5没有关系。

于是我们可以得到两个重要的结论：

1. 在一段区间内，以区间内的最大值为界，最大值左侧与最大值右侧的值之间不会互相影响。
2. 在一段区间内，这个区间的最大值一定会出现在最大值里。

有了这两个结论，我们就能大约想到通过区间最大值来划分子问题。我们直接根据题意定义dp[m][n][k]，并尝试按照区间最大值来推导状态转移方程。
由于结论2，我们不难想到dp[m][n][k]一定只和dp[m-1][?][?]有关。
由于结论1，我们可以进一步发现$$dp[m][n][k]=\sum_{left\_n=0}^{n-1}\sum_{k'=0}^k C_n^{left\_n}\cdot dp[m-1][left\_n][k']\cdot dp[m-1][(n-1)-left\_n][k-k']$$其意思是对于n个数，除去最大值之后，我在左边选择left_n个数，并且让左边恰好有k'个good number。这样右边就自然的要选(n-1)-left_n个数，并且要恰好有k-k'个good number。
最后结合一开始m=1时的结论即可。

代码

Java

C++