PDF《NOI 模拟赛试题讨论》

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOI 模拟赛试题讨论 wzj52501 Peking University

2018 年11 月26 日wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Results wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . password 玄机 求出至少包含 m 个模板串各一次的长度为 n 的匹配串有多少个,答案 对998244353 取模. m ≤ 4, ∑ |str| ≤ 50, n ≤

109 wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 7. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 7. 直接枚举长度为 n 的所有密码串,分别检验即可. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 7. 直接枚举长度为 n 的所有密码串,分别检验即可. 时间复杂度为 O(n2 * 10n ). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 进一步的分析 面对这种多串匹配的问题,我们自然联想到了 AC 自动机. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 进一步的分析 面对这种多串匹配的问题,我们自然联想到了 AC 自动机. 首先对 m 个串建立 AC 自动机模型,这样我们就可以把问题转化 成下面的形式: 在一个 DAG 上行走 n 步,要求所经过的结点包含了 m 个给定结点. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 2501. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 2501. 设f(i, j, S) 表示已经走了 i 步,当前在结点 j,已经包含的特殊结 点集合为 S 的方案数. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 2501. 设f(i, j, S) 表示已经走了 i 步,当前在结点 j,已经包含的特殊结 点集合为 S 的方案数. 转移时枚举第 i +

1 步走了哪一条边(相当于枚举密码串的第 i +

1 位填写了哪个数字) ,如果是数字 c 对应的那条边,则f(i, j, S) → f(i + 1, trans(j, c), S2). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 2501. 设f(i, j, S) 表示已经走了 i 步,当前在结点 j,已经包含的特殊结 点集合为 S 的方案数. 转移时枚举第 i +

1 步走了哪一条边(相当于枚举密码串的第 i +

1 位填写了哪个数字) ,如果是数字 c 对应的那条边,则f(i, j, S) → f(i + 1, trans(j, c), S2). 初始将 f(0, 0, 0) 设为 1,答案即为 ∑∑ |str| j=0 f(n, j, all). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 2501. 设f(i, j, S) 表示已经走了 i 步,当前在结点 j,已经包含的特殊结 点集合为 S 的方案数. 转移时枚举第 i +

1 步走了哪一条边(相当于枚举密码串的第 i +

1 位填写了哪个数字) ,如果是数字 c 对应的那条边,则f(i, j, S) → f(i + 1, trans(j, c), S2). 初始将 f(0, 0, 0) 设为 1,答案即为 ∑∑ |str| j=0 f(n, j, all). 时间复杂度为 O(n * ∑ |str| * 2m ). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .