QAQ

闲得无聊一口气注册了8个左右的小号...

尴尬

我$fpdqwq$，就是饿死，死外面，也要当毒瘤

哈哈哈哈哈

佛曰：冥悉藐諳恐集陀若道想輸者依礙逝遠俱咒罰若

感谢选手提供不一样的解法！ 出题人也在这场比赛学到了很多！

题目背景来源于某个伟大的东洋人(ZUN)创作的童话故事。

我们将在每道题下面公示在比赛中AC了这道题的选手。

小猫咪和小狐狸

在本题中，小猫咪的名字叫橙，小狐狸的名字叫八云蓝。

AC:

peehs_moorhsum

zbw001

本来计划是按照难度排序的，因为这道题有数学做法。

然而结果有些出乎意料...

不过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:

orangebird

peehs_moorhsum

wujiuwu

he_____he

通过这个题目的人不少。这个题可以说是比较开放。

怎么能说是正解被踩了呢？本来放$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分

小猫咪和小乌鸦

在本题中，小猫咪的名字叫火焰猫燐，小乌鸦的名字叫灵乌路空。

peehs_moorhsum

AKEE

Hhzzkk

你可能不是不会做这个题，只是时间不够了。

怎么卡乱搞啊，好气啊

算法一

随便写个爆搜，枚举每个基团的值是多少并判定是否合法。

时间复杂度：$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 ！

他是个好人！

祝福的话不是很会说。

第二类斯特林数 $S(n,m)$ 表示将 $n$ 个元素放入 $m$ 个无序集合的方案数。

递推形式

递推式: $S(n,m)=mS(n-1,m)+S(n-1,m-1)$

证明:

考虑第 $n$ 个元素所在集合。

$1.$ 如果第 $n$ 个元素被放在一个之前就存在的集合。

$--$在放入第 $n$ 个元素之前，共有 $n-1$ 个元素，$m$ 个集合。方案数为 $m*S(n-1,m)$。

$2.$ 如果第 $n$ 个元素被放在一个之前不存在的集合。

$--$在放入第 $n$ 个元素之前，共有 $n-1$ 个元素，$m-1$ 个集合。第 $n$ 个元素构成一个单独的集合，方案数为 $S(n-1,m-1)$。

综上, $S(n,m)=mS(n-1,m)+S(n-1,m-1)$ 。

这种考虑最后一个元素的情况并进行递推的思想，在某些题目当中同样适用，并不仅限于第二类斯特林数公式的推导。

容斥形式

咕咕咕。

容斥形式可以在 $O(好多)$ 的时间复杂度求出就那么多个第二类斯特林数。

Meow Round #1 将于 5 月 10 日举行，欢迎校内外同学参加。

本场比赛将以可爱的猫作为主题!

比赛一共包含三道题目，记Rating。

比赛时间

北京时间 2018 年 5 月 10 日 19:35~22:35

出题阵容

Petr Um_nik Syloviaely V--o_o--V tourist 等 Codeforces Legendary Grandmaster

都没有参与出题!

题目提供者：三道题均由 fpdqwq 提供

验题人：jjikkollp

比赛难度

出题人认为，比赛难度约为NOIP提高+ 强省省选- 。

特别提示

注意比赛在APIO2018报道当晚哦！大家可以晚上一起在酒店开黑...? (最好不要交流吧)

出题人不善写题面，风格可能很会诡异，希望选手自己提高语文的学素术养。

参加本场比赛有机会获得金牌叶教练躺椅使用权一次!

提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

我稳了