OI Problems   关于

#w7t42l. 益智游戏(game)

时间限制:2 s       空间限制:512 MiB       标签: 缺题解 

算法难度等级:0       思维难度等级:0       实现难度等级:0


本题来源于:2023 年 9 月 2 日多校联赛提高组第 2 题

麦哲伦有 nn 个无人机,第 ii 个无人机有一个正整数参数 aia_i,其中 ai[1, m]a_i\in[1,\ m]

麦哲伦每次会使用 [l, r][l,\ r] 范围内的无人机进行高效制冷。她需要手动配置 bl, bl+1, , brb_l,\ b_{l+1},\ \cdots,\ b_r,使得 bi=aib_i=a_i,才可以启动高效制冷模块。

但由于无人机实在是太多了,配置的过程很容易出错,因此她改进了配置系统,现在只需要序列 al, al+1, , ara_l,\ a_{l+1},\ \cdots,\ a_rbl, bl+1, , brb_l,\ b_{l+1},\ \cdots,\ b_r 的最长公共子序列的长度恰好rlr-l,就可以启动高效制冷模块。

为了保证无人机的正常运行,bib_i 也必须是 [1, m][1,\ m] 范围中的正整数。

麦哲伦想知道,对于每一次的高效制冷,她有多少种配置序列 bl, bl+1, , brb_l,\ b_{l+1},\ \cdots,\ b_r 的方式。两种配置方式 b, cb,\ c 不同,当且仅当存在 i[l, r]i\in[l,\ r],使得 bicib_i\neq c_i

由于答案太大了,她只想知道答案对 998244353998244353 取模后的结果。

输入格式

从文件 freeze.in 中读入数据。

第一行三个整数 n, m, qn,\ m,\ q,分别表示无人机的个数、参数的范围和高效制冷的次数。

第二行 nn 个正整数,表示每个无人机的参数 a1, a2, , ana_1,\ a_2,\ \cdots,\ a_n

接下来 qq 行,每行两个正整数 l, rl,\ r,表示一次高效制冷所选的无人机范围。

输出格式

输出到文件 freeze.out 中。

对于每次高效制冷,输出一行一个整数,表示答案。

3 3 3
1 1 1
1 1
1 2
1 3
2
4
6

样例 1 解释

对于第一次高效制冷,{2}, {3}\{2\},\ \{3\} 两个序列满足要求。 对于第二次高效制冷,{1,2}, {1,3}, {2,1}, {3,1}\{1,2\},\ \{1,3\},\ \{2,1\},\ \{3,1\} 四个序列满足要求。 对于第三次高效制冷,{1,1,2}, {1,1,3}, {1,2,1}, {1,3,1}, {2,1,1}, {3,1,1}\{1,1,2\},\ \{1,1,3\},\ \{1,2,1\},\ \{1,3,1\},\ \{2,1,1\},\ \{3,1,1\} 六个序列满足要求。

10 9 1
1 2 1 3 1 4 5 6 7 8
1 10
789

数据范围

对于 100%100\% 的数据,满足 1lrn5×1051\leq l\leq r\leq n\leq 5\times 10^52m1092\leq m\leq 10^91q2×1061\leq q\leq 2\times 10^6

子任务编号 分值 nn\leq mm\leq qq\leq
11 55 1010 1010 1010
22 1919 10001000 10910^9 10001000
33 2222 2×1052\times 10^5 10910^9 10001000
44 3434 2×1052\times 10^5 10910^9 3×1053\times 10^5
55 2020 5×1055\times 10^5 10910^9 2×1062\times 10^6