【N230919C】名额限制
简述题意：省队，\(k\) 分之一限制。总共 \(n\) 个人，\(m\) 所学校，按分数高到低给出每个人是否进队。求满足题目要求的前提下，每个人所在学校的情况总数。
首先将最后一个进队的人后的人删去，每个人的学校情况相互独立。设 \(t\) 表示省队人数，令 \(lim=\lfloor\dfrac{t}{k}\rfloor\)。
DP：设 \(f_{i,j}\) 表示考虑了前 \(i\) 个人，有 \(j\) 所学校进队人数达到限制。
转移：
- 第 \(i\) 个人没有进队，\(f_{i,j}\gets f_{i,j}\times j\)，他所在的学校进队人数必须达到限制。
- 第 \(i\) 个人进队，发现状态 \(j\) 不好维护。不直接维护 \(j\)，转而当第 \(i\) 个人作为校线最后一名时，再将该校所有人放入。
两种情况：1. \(f_{i,j}\gets f_{i-1,j}\)，第 \(i\) 个人不是校线最后一名。2. \(f_{i,j}\gets f_{i-1,j-1}\times C_{s_i-1-lim\cdot (j-1)}^{lim-1}\times (m-j+1)\) 校线最后一名，从 前面进队的人中选择出 \(lim-1\) 个人，和 \(i\) 组成未被限制的 \((m-j+1)\) 所学校中的一所。
然而有学校未被限制，上述转移没有考虑它们的贡献，进一步考虑。
枚举被限制学校数 \(i\)，有 \(t-i\cdot lim\) 个人未考虑所在学校，且还剩下 \(m-i\) 所学校未考虑。他们需满足任意一所学校进入省队的人数 \(<lim\)。将他们单独拎出来 DP。
设 \(g_{i,j}\) 表示 \(i\) 个人，来自 \(m-j\) 所学校，每所学校的人数 \(<lim\) 的情况数。
枚举一所学校放入的人数，容易转移，但复杂度劣，考虑将人一个一个加入。
转移时用总方案减去不合法的方案数 \(g_{i,j}\gets (g_{i-1,j}-g_{i-lim,j+1}\times C^{lim-1}_{i-1})\times (m-j)\)。
分析复杂度：\(\lfloor\dfrac{t}{lim}\rfloor\le k\)，\(j\) 仅需要 \([0,k]\) 即可，因每次从 \(i-lim\) 转移，\(j\) 最多加 \(k\) 次，维护 \(j\in[0,2k+1]\) 的 DP 值即可。
最后答案：\(\sum\limits_{i=0}^{i\le \lfloor{\frac{t}{lim}}\rfloor}f_{t,i}\cdot g_{t-i\cdot lim,i}\)。