【NOI联考by ysy】庆典

2016年6月17日6300
【题目描述】

战狂在昌和帝国的首都法法城召开了庆典,向一万名最杰出的士兵分发了用魔法猪做的猪肉饺子,士兵们吃了猪肉饺子后,战斗力大幅提高。

为了保护战狂的安全以及维护现场秩序,大预言家抽调了n名普通士兵组成了m个小队完成一些不同的任务。由于一些特殊的原因,所有小队的人数都互不相同。

你需要求出有多少种可能的组队方案。注意士兵是相同的,而小队是不同的。

【输入数据】

第一行两个个整数n,m。

【输出数据】

一行一个数表示答案。对998244353取模。

【样例输入】

16 4

【样例输出】

216

【数据范围】

对于20%的数据,n,m<=20。

对于50%的数据,n,m<=3000。

对于100%的数据,n,m<=100000。

【题解】

先分组再给组标号,即要求组的大小从小到大,分完以后将方案乘上m!

对于20%的数据,f[i][j][k]表示前i个人分j组,最后一组有k个人,n^4 递推

对于50%的数据

我们发现上一个算法的瓶颈在于,要考虑前一组分了多少个人,这样很麻烦

我们可以考虑只用f[i][j]表示前i个人分j组,之后的m-j组先分配和最后一组同样的人数,那么在考虑后面分组的时候,就不用考虑递增的问题了

这样直接递推是nm^2

其实很容易发现,m*(m+1)/2显然无解,那么m^2应当与n同级,直接特判完dp即可

对于100%的数据

上一个递推算法可以用一些技巧优化到nm,不过比较麻烦

我们可以考虑,首先给第i个小队分配i个人,接下来为了保证人数递增,每次给第i至n个小队增加1个人。

那么答案相当于将n-m*(m+1)/2做1-m的自然数拆分,这个递推比较简单。

复杂度n*m

20%

50%

100%