杜老师给我讲的一道 DP 题～

题目描述

某省省选，共个参赛选手，来自所学校，省队名额为人，每个学校最多进入个省队。决定省队名单的方案如下：将所有选手按成绩从高到低排序，如果加上这一位选手后，名单中的人数不超过人，并且每个学校在名单中的人数不超过，就让这位选手进队，否则就不让。

给定，以及按照成绩从高到低排序后（可以认为不会出现相同分数），每个人是否进入了省队，你需要求出在省队总名额与进入省队人数相等的前提下，每个人所在学校的可能状态数。两个状态不同当且仅当存在一个人两个状态中所在的学校不同。答案可能很大，输出答案即可。

当然，你无法保证名单的正确性，所以答案可能为。

输入格式：

第一行包含三个正整数，表示参加省选的人数，学校的个数，名额限制的比例。

第二行包含了一个长度为的串，第位为表示第个人没有进省队，否则进了省队。

输出格式：

一行，表示可能的状态数。

这题的做法很抽象，将两个抽象方案的统计合在一起才能完成对原问题方案的统计。

设，同时设表示前个人中进省队的人数：

思路的出发点是这样的。如果，意味着第个人被学校杀了，也就是说前个人中恰有个人和这个人属于一所强校。于是我们设表示考虑前个人，恰好有所强校，这些强校皆有个人进省队，剩下个是不属于强校的杂鱼，这样的不同强校与杂鱼选手的位置的方案数。

形式化地，设长度为的序列表示第个人属于第个学校（）的方案，同时我们设一个布尔函数表示在方案中，是否是强校：

（注意，一个学校不可能有多于个人进队）则我们认为两个方案等价当且仅当：

  1. 对于任意，存在。即两个方案同一个位置上的人要么都属于强校，要么都是杂鱼；
  2. 对于任意，存在。即方案中的两个人如果都属于强校，那么这两个人要么在两种方案中都属于同一个学校，要么都不属于同一个学校。

换句话说两个方案相同当且仅当任意选手的关系是相同的。这里的关系指是否是强校 / 杂鱼，强校还要区分是否是同一所强校。

于是表示使用上述规则的不同的方案数。转移时枚举第个人是否进省队：

  1. 进省队，则枚举是强校选手 / 杂鱼；如果是强校选手就枚举它属于哪一个强校（枚举个人和他组一个强校）；如果是杂鱼就直接用的方案转移。
  2. 学校杀，则他一定是强校选手，枚举是哪一个强校。

综上得到：

边界。

接下来我们考虑杂鱼的学校选择的方案统计。

设表示恰好有所强校满人进队，剩下个杂鱼进队的学校选择（但不考虑强校是哪所学校）的方案数。相当于总共有个人进队。注意这里指的是所有人进队！相当于把进队的人方案计算出来，最后乘上一个。

我们同样用形式化的语言描述。设长度为的序列为第个人属于第个学校（）的方案。关于的定义与上文相似，表示前个人中是否是强校。则两个方案等价当且仅当

  1. 对于任意，存在。
  2. 对于任意，存在。即杂鱼选的学校要一样。

通俗地说，就是把杂鱼的学校的具体选择考虑进去了。但这里不要求区分不同强校选手之间的位置关系（因为这个关系已经在中被讨论过了），但会考虑强校与杂鱼选手之间的位置关系。

转移的时候枚举最后一个人是哪个杂鱼学校，他只能在所学校中选择。但这样有一个 Bug，就是可能他选了一个之后使得另一个学校刚好满个人进队，成为强校（即的状态），因此要减掉这种不合法的状态：

边界。转移的时候倒着转移即可。

最后统计答案，设：

其中，即的次下降幂。这个式子可以理解为，枚举强校个数，枚举不同强校与杂鱼之间的位置关系，枚举杂鱼的学校选择方案，枚举强校的学校选择方案，这样统计方案数。

总复杂度。