#P7424. 碎梦
碎梦
碎梦
题目背景
「从我又小又拥挤的房间」 「从我堆满了贪念的床边」 「飞向总有容身处的世界」
「却碎裂\ 却碎裂」
——「碎梦」COP,洛天依
多年以后,算法竞赛的一切对于忆哀来说是什么呢?一个光辉而没有结局的梦罢了。
永恒的梦,失落的梦,无望的梦,破碎的梦。
仿佛是想到了什么,她又从纸箱里拿出落了几层灰的笔记本,好不容易找出旧时代的充电插头。随着散热风扇的嗡鸣声,一个尘封的世界再次展现在她眼前,还觉得自己只要稍微看看问题,就有可能抽丝剥茧理清问题的思路,那只是逞强罢了。
“第二类斯特林数怎么求来着?”这个问题突然从她脑中浮现。
是啊,她曾经深深扎入各种组合计算中流连忘返,但如今已经连这些基础也不甚记得了。
题目描述
第二类斯特林数 表示将 个不同元素划分为 个非空集合的方案数,集合之间不计顺序。
忆哀使用朴素递推式
初值为 ,()。要么第 个元素单独构成集合,要么把它放入已有的 个集合之一。
她的程序如下,数组初始为 ,另将 设为 :
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= min(i, m); ++j)
f[i][j] = (f[i - 1][j - 1]
+ j * (long long)f[i - 1][j]) % 998244353;
可以认为数组越界部分的值为 ,并且计算机可以存下 的数组。
程序本应输出 ,但在计算完某些位置 后,写入发生意外,该位置实际被赋值为 。这样的意外在 个不同位置发生。
求经过全部意外后,程序实际得到的 。之后的递推会使用已被改写的值。
输入格式
第一行三个整数 。
接下来 行,每行三个整数 ,表示 计算完成后实际写入的值。意外按程序执行顺序给出,即先按 、再按 严格字典序递增。
输出格式
输出一个整数,表示实际的 。
样例输入1
5 3 1
1 0 1
样例输出1
31
样例输入2
1000 100 0
样例输出2
958221900
数据范围
所有数据满足 ,,。每次意外满足 ,,,所有 不同并按上述顺序给出。
| 测试点 | 上限 | 上限 | |
|---|---|---|---|
| 1—6 | 500 | ||
| 7—9 | 10 | ||
| 10—11 | |||
| 12—14 | |||
| 15—17 | 500 | ||
| 18 | |||
| 19—20 |