感谢选手提供不一样的解法！ 出题人也在这场比赛学到了很多！
题目背景来源于某个伟大的东洋人(ZUN)创作的童话故事。
我们将在每道题下面公示在比赛中AC了这道题的选手。
小猫咪和小狐狸
在本题中，小猫咪的名字叫橙，小狐狸的名字叫八云蓝。
AC:
本来计划是按照难度排序的，因为这道题有数学做法。
然而结果有些出乎意料...
不过OGF还是给了100的，很良心(fake
算法一
"小猫咪...给小狐狸提出了这样一个问题：将这些食物全部放进 $m$ 个本质相同的盒子里，不能有空盒子，一共有多少种方案。"
枚举每一种方案并进行计算。
时间复杂度：$O(n*bell(n))$
期望得分：$10$分
算法二
"如果你超过10分钟都对这道题没有思路，推荐阅读fpdqwq关于第二类斯特林数的简要介绍。"
通过阅读blog得到提示，记$f(n,m)$为题目所定义的权值和(即答案)，通过枚举最后一个元素所在的集合大小进行状态转移，进行递推。
递推式:$ f(n,m)= Σ(i * f(n-i,m-1) * C_{n-1}^{i-1})) $
其中 $i$ 为所枚举的最后一个元素所在集合的大小，$C_i^j$为组合数。
时间复杂度：$O(n^2 * m)$
期望得分：$40$分
如果你对快速数论变换 $NTT$ 没有了解，请查阅相关资料或者自行跳转算法五。
算法三
"注意要对 $998244353$ 取模。"
发现上面的递推式满足卷积形式，并且模数是 $ UOJ $ 通用模数。
运用 $NTT$ 加速每次从 $f(i,m)$ 到 $f(i,m+1)$ 的运算。($ 1 \leq i \leq n $)
时间复杂度：$O(n*m*logn)$
期望得分：$70$分
算法四
"他们真是太强了。"
zbw001 和 peehs_moorhsum 使用了这种做法。%%%
多项式 $ \frac{n!}{m!} * (Σ \frac{x^i}{(i-1)!} )^m$ 的 $n$ 次项系数即为答案。通过 $ NTT $ 倍增卷积计算即可。
如果你对生成函数有了解，请自行跳转算法五。
我们先不妨考虑以下问题:
1.求不定方程 $ n=A_1+A_2+...+A_m $ 的正整数解的数量。其中 $ A_i $ 为变量，$ N,m $ 为给定常量。
记 $ S_n= Σ x^i $ ($ 1 \leq i \leq n $)
多项式 $ S_n^m $ 的 $n$ 次项系数即为答案。
考虑 $ S_n^m $ 的展开式: 由乘法原理，展开式共有 $ n^m $ 项。
感性理解: $S_n^m = (x + x^2 + ... + x^n) * (x + x^2 + ... + x^n) * ... (x + x^2 + ... + x^n)$ 展开式的每一项是从 $ m $ 个 $ (x + x^2 + ... + x^n) $ 各取一项，相乘所得的积。
我们不妨记从第 $i$ 个 $ (x + x^2 + ... + x^n) $ 取出的项为 $x^{Ai}$，那么对于每一个 $ x^n $项，$ x^n = x^{A_1} * x^{A_2} * ... * x^{A_m} $
即 $ n=A_1+A_2+...+A_m $ 。即: 每一个 $ x^n $项对应一组正整数解。
2.将 $n$ 个本质相同的食物放进 $m$ 个本质相同的盒子里，不能有空盒子，一共有多少种方案。
与问题1一点也不类似。可以先不管这个问题。
3.将 $n$ 个本质不同的食物放进 $m$ 个本质相同的盒子里，不能有空盒子，一共有多少种方案。
与问题1类似。问题1相当于问题3的"盒子本质不同"的版本。
考虑食物本质不同对方案的影响:不妨假设在某个问题1的方案中,$m$个盒子内食物的数量分别为$A_1,A_2...A_m$。 那么它在问题3中，对应了$n!/(A_1! * A_2! * ... A_m!)$种方案。读者不妨想一想，为什么。(这里提供一种感性理解方式)
感性理解:在问题1中，食物是有序的。而在问题2中，划分出的每个集合内部的食物是无序的。 考虑 $m=n$ 的情况下，此时每个集合大小为1，每个问题3的答案对应了 $n!$ 个问题1的答案。 如果集合大小不为1，便要对每个集合进行"消序"，即答案除以$(A_1! * A_2! * ... A_m!)$
用类似的方式构造多项式$ \frac{n!}{m!} * (Σ \frac{x^i}{i!} )^m$ , $ n $ 次项系数即为答案。
4.给问题3中每一个方案赋一个权值，大小为每个盒子内食物个数的乘积。
在问题3的多项式的基础上进行构造，即可得出答案。
时间复杂度 $O(n*logn*logm)$
期望得分：$100$分
算法五
“咕咕咕。”
事实上，这道题有更加简便的满分做法:
$ C_n^m * m^{n-m} $即为答案。
考虑每个集合划分方案的权值，即每个集合的元素个数的乘积:可以看做从每个集合取出一个元素，共$m$个，有多少种不同的组合方式。
所有的权值和，即对于每种集合划分方案的“组合方式”的种数求和。
我们不妨从$m$个元素的组合方式的角度来求和。
所有的权值和可以看作是:对于每种“$m$个元素的组合方式”，统计它被多少种集合划分方案“包含”。
则要求上述“组合方式”内的$m$个元素在$m$个不同的集合中。其余的$n-m$个元素在$m$个集合中任选即可。
便可得出答案:$ C_n^m * m^{n-m} $。
期望得分: $100$分
如果有不明白欢迎来私信提问。或者有错误也请来指正。
小猫咪和小老鼠
在本题中，小老虎的名字叫寅丸星，小老鼠的名字叫纳兹琳。
就是一个非常$trivial$的最长上升子序列啊...
AC:
通过这个题目的人不少。这个题可以说是比较开放。
怎么能说是正解被踩了呢？本来放$O(n^3)$的做法就是能过呀！
算法一
记 $f(i,j)$ 为以 $(i,j)$ 为最后一个开采点，最多开采了几个碎片。
枚举 $ i' \leq i , j' \leq j $ ，$ (i',j') $ 为开采 $ (i,j) $ 前的上一个开采点。
$ f(i,j)= max( f(i',j') )+1 $ ，其中 $ A(i',j') \leq A(i,j) $。
时间复杂度：$O(n^2 * m^2)$
期望得分：10分
算法二
对算法一进行优化，每行开一个树状数组。
被吐槽了。反正我也说不清楚，你们还是直接看二维树状数组的解法三吧。 反正会了正解这个自然会了。
总之能够每行开一个树状数组。如果你不太会写二维的话写个一维的可能能拿40分。
这做法不是我瞎编的，部分分程序可以看验题人的50分代码。
时间复杂度：$O(n * m^2 * logn)$
期望得分：40分
实际得分：50分
算法三
wujiuwu 使用了这种做法并AC了。(其他这么写的选手全都MLE了$QAQ$)%%%
我们用与算法一相同的$dp$方式：$ f(i,j)= max( f(i',j') )+1 $ 。
由于直接枚举所有 $ (i', j') $ 过于低效，我们考虑用数据结构进行优化。
我们考虑将关于一个整点的所有信息看作一个struct:$(i,j,A(i,j),f(i,j))$
那么 $f(i,j)$ 能够从 $f(i',j')$ 转移，等价于$ i' \leq i $，$ j' \leq j $，$ A(i',j') \leq A(i,j) $ 同时成立。
不妨把$(i,j,A(i,j))$看作一个$3$维向量。那么转移限制便可以看做是$3$维偏序。
对其中一个维度作为第一关键字，另外两个维度作为第二，三关键字排序，并按照顺序进行转移。
每当转移完成，将另外两个维度的值作为坐标位置，把 $f(i,j)$ 存入二维树状数组里(单点修改)，查询二维前缀$max$。
这样，第一个维度的大小关系通过排序满足，另外两个维度的大小关系通过数据结构的查询操作来满足。
就在满足$3$个维度的偏序的情况下求出了$max$。
细节(废话):如果那个位置原来有值，就和那个位置的值取$max$。
值得一提的是，如果取 $ A(i,j) $ 作为第一个维度，那么二维树状数组空间就是$O(n * m)$的。
如果取$i$作为第一个维度，$ A(i,j) $ 的值域是 $ n * m $ 的，二维数组空间就是$O(n * m * m)$的。
虽然出题的时候没有仔细构造数据，离散化一下也能过，或者用其他的方法卡一卡...但是还是有不少选手MLE...$QAQ$
我要卡你们的话就把值域出成 $ A(i,j) \leq 10^9$ 了，说不定有选手就去写二维线段树了(逃
时间复杂度：$O(n * m * logn * logm)$
期望得分：100分
实际得分：50分 或 60分 或 100分
算法四
没错这是我原先的想法。
本来想随便出一个分治优化dp的，没想到有这么多做法。可是好写又好想为什么没有人这么做呢？
具体怎么做就不介绍了，可以参考$NOI2007cash$。
时间复杂度：$O(n * m * logn * logm)$
实际得分：100分
算法五
考虑另一种dp方式： 记 $f(i,j,k)$ 为以 $(i,j)$ 为最后一个开采点，开采了 $ k $ 个碎片时的最小开采难度。
这句话居然听起来不别扭！
转移显然$O(1)$。哦，担心内存会爆的话可以滚动数组。
$ k \leq n+m $
时间复杂度：$O(n * m * ( n + m ) )$
实际得分：100分
小猫咪和小乌鸦
在本题中，小猫咪的名字叫火焰猫燐，小乌鸦的名字叫灵乌路空。
你可能不是不会做这个题，只是时间不够了。
怎么卡乱搞啊，好气啊
算法一
随便写个爆搜，枚举每个基团的值是多少并判定是否合法。
时间复杂度：$O(AC)$
期望得分：10分
算法二
考虑针对$ l==r $ 的数据设计算法：
首先忽略每个基团的值要非负的约束，随便代入一个值解出所有基团的值。
考虑把所有α-基团 $ +x $ β-基团 $ -x $ 满足所有联系的约束。
通过上述方法调整得到最优解。
时间复杂度：$O(n+m+k)$
期望得分：20分
结合算法一：30分
算法三
考虑$HNOI2013$切糕，把代码$copy$下来随便改一改，能过小数据。
没做过也没关系，反正这玩意比正解还难写。
你还要推式子，有这功夫不如写正解。
期望得分：30分
结合算法二：60分
算法四
考虑差分约束系统。
记 $ A_i $ 为第 $ i $ 种α-基团的数量，$ B_i $ 为第 $ i $ 种β-基团的数量。
记 $ C_i = - B_i $。
则联系带来的约束可以转化为：$ l \leq A_i - C_j \leq r$，$ C_j \leq 0 \leq A_i $
求 $ ΣA_i + ΣC_j $ 的最大值。
百度"差分约束系统"有真相：$SCOI2011$糖果
如果细节想不清楚的话，请私信我或者在下面提问...
时间复杂度: $O(spfa(n+m+k))$
卡$spfa$的出题人都是毒瘤
期望得分：100分
算法五
问 Hhzzkk
这个家伙会乱搞，很有毒！
jjikkollp
感谢验题人 jjikkollp ！
他是个好人！
祝福的话不是很会说。
