U227884 [sxyz NOIP 模拟赛]4 lis 问题（lis）

[sxyz NOIP 模拟赛]4 lis 问题（lis）T4 ------------ 2s 512MB

最长上升子序列是一个经典问题。相信大家在学习 OI 的过程中都对这个问题有了深入的理解。为了考察大家的理解程度，出题人精心准备了一道题送给大家。 相信大家都对最长上升子序列的 dp 都非常熟悉。这里介绍一下本题中求 lis 的 dp状态：令 fi 表示以第 i 个元素结尾的所有子序列中（第 i 个数字必须被选中）。设计出状态后即可进行简单的 dp。由于 dp 过程在本题中并不重要，因此题面中不作赘述。在本题中，我们将忽略 dp 的具体过程，转而对 fi 的值进行深入的研究。 在昨天的题目中，我们提到了排列。今天的这道题也与排列有关。数组 ai 是一个1 − n 的排列，你并不会知道这个排列长什么样。出题人对这个排列通过上面的算法求出了 fi 的值，并将 fi 的值提供给你，并希望你能够还原这个排列。然而经过细致的研究，出题人发现， fi 的值对排列的限制是非常宽松的，也就是说，仅通过 fi 的值并不能唯一地还原排列。 为了让这道题能够具有唯一的输出，出题人转而决定，你需要求出 ansi 表示这个排列中 ai 可能的最大值。由于输出规模可能很大，你只需要输出 $\sum\limits^n_{i=1}131^i\;∗\;ans_i\bmod 998244353$ 的结果。

由于数据范围较大，本题采用数据生成器进行读入。你只需要读入三个整数 n, lim, seed并使用下发的数据生成器即可，其中数据生成器中的函数前三个参数依次为你读入的整数，第四个参数为你希望保存数据的数组。其中数据生成器将会保证存在一个排列，使得这个排列通过上述 lis 算法后能得出生成的 f 数组，且 1 ≤ fi ≤ lim。

一行一个整数，表示你的答案。

4.4 样例解释 样例 1 生成的 f 数组为 1 2 3 3 1 样例 1 的 ans 数组为 2 3 5 4 1 样例 2 生成的 f 数组为 1 1 2 1 3 4 4 2 5 3 样例 2 的 ans 数组为 10 4 6 1 7 10 8 4 10 6 4.5 数据范围与提示 对于 10% 的数据， n ≤ 9 对于 50% 的数据， n ≤ 5000 对于 70% 的数据， n ≤ 10$^5$ 另有 10% 的数据， lim = 2 另有 10% 的数据， lim = 10 对于所有数据， 1 ≤ lim ≤ n ≤ 10$^7$, 1 ≤ seed ≤ 10$^9$