#P7424. 碎梦

    ID: 7438 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>组合数学动态规划字符串CF2400模运算数学

碎梦

碎梦

题目背景

「从我又小又拥挤的房间」 「从我堆满了贪念的床边」 「飞向总有容身处的世界」

「却碎裂\ 却碎裂」

——「碎梦」COP,洛天依

多年以后,算法竞赛的一切对于忆哀来说是什么呢?一个光辉而没有结局的梦罢了。

永恒的梦,失落的梦,无望的梦,破碎的梦。

仿佛是想到了什么,她又从纸箱里拿出落了几层灰的笔记本,好不容易找出旧时代的充电插头。随着散热风扇的嗡鸣声,一个尘封的世界再次展现在她眼前,还觉得自己只要稍微看看问题,就有可能抽丝剥茧理清问题的思路,那只是逞强罢了。

“第二类斯特林数怎么求来着?”这个问题突然从她脑中浮现。

是啊,她曾经深深扎入各种组合计算中流连忘返,但如今已经连这些基础也不甚记得了。

题目描述

第二类斯特林数 f(n,m)f(n,m) 表示将 nn 个不同元素划分为 mm 个非空集合的方案数,集合之间不计顺序。

忆哀使用朴素递推式

f(n,m)=f(n−1,m−1)+mf(n−1,m),f(n,m)=f(n-1,m-1)+m f(n-1,m),

初值为 f(0,0)=1f(0,0)=1,f(0,m)=0f(0,m)=0(m≠0m\ne0)。要么第 nn 个元素单独构成集合,要么把它放入已有的 mm 个集合之一。

她的程序如下,数组初始为 00,另将 f[0][0]f[0][0] 设为 11:

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;

可以认为数组越界部分的值为 00,并且计算机可以存下 (n+1)×(m+1)(n+1)\times(m+1) 的数组。

程序本应输出 f(n,m) mod 998244353f(n,m)\bmod998244353,但在计算完某些位置 f(xi,yi)f(x_i,y_i) 后,写入发生意外,该位置实际被赋值为 ziz_i。这样的意外在 kk 个不同位置发生。

求经过全部意外后,程序实际得到的 f(n,m)f(n,m)。之后的递推会使用已被改写的值。

输入格式

第一行三个整数 n,m,kn,m,k。

接下来 kk 行,每行三个整数 xi,yi,zix_i,y_i,z_i,表示 f(xi,yi)f(x_i,y_i) 计算完成后实际写入的值。意外按程序执行顺序给出,即先按 xix_i、再按 yiy_i 严格字典序递增。

输出格式

输出一个整数,表示实际的 f(n,m) mod 998244353f(n,m)\bmod998244353。

样例输入1

5 3 1
1 0 1

样例输出1

31

样例输入2

1000 100 0

样例输出2

958221900

数据范围

所有数据满足 1≤n≤9×1081\le n\le9\times10^8,0≤m≤min⁡(n,105)0\le m\le\min(n,10^5),0≤k≤200\le k\le20。每次意外满足 1≤xi≤n1\le x_i\le n,0≤yi≤min⁡(m,xi)0\le y_i\le\min(m,x_i),0≤zi<9982443530\le z_i<998244353,所有 (xi,yi)(x_i,y_i) 不同并按上述顺序给出。

测试点 nn 上限 mm 上限 kk
1—6 10310^3 500 =20=20
7—9 9×1089\times10^8 10
10—11 10210^2 =0=0
12—14 =20=20
15—17 500
18 10510^5 =0=0
19—20 =20=20