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

Submission #130708556 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #130710192 - Codeforces
Codeforces. Programming competitions and contests, programming community