P11959 「ZHQOI R1」Poetry

 淡く煌(きらめ)く傷口が 瞬間 世界を止めて ------------ なかきよの とおのねふりの みなめさめ なみのりふねの おとのよきかな.

Given a positive integer $ k $, the character set size for this problem is $ k $. We use positive integers $ i $ to denote the $ i $-th character in the set. Given a positive integer $ m $, a string $ \mathcal{S} $ is defined as **"harmonious"** if and only if either: - The length of $ \mathcal{S} $ is less than $ m + 2 $ ,or - After deleting **any** $ m $ characters from $ \mathcal{S} $, there exists no contiguous palindromic substring of length greater than $1$ in the resulting string. You need to process $ q $ queries. For each query, given a "harmonious" string $ T $ of length $ m + 2 $ and a non-repeating character set $ U $, determine the number of strings of length $ n $ that satisfy the following conditions: 1. $ T $ is a prefix of the string. 2. The string is "harmonious". 3. The last character of the string belongs to $ U $. Output the answer modulo $ 998244353 $. For all queries in a test case, $ k $ and $ m $ remain the same. **Note: It is guaranteed that $k-m \ge 3 $.**

The first line contains an integer $ c $ representing the test case ID. In sample inputs, $ c = 0 $. The second line contains four integers $ q, k, m $, representing the number of queries, the character set size, and the constant used to define "harmonious" strings. Each of the next $ q $ lines describes a query, containing: - An integer $ n $, - A sequence $ T $ of $ m + 2 $ positive integers (the "harmonious" prefix), - An integer $ |U| $ (the size of set $ U $), followed by $ |U| $ distinct integers denoting the elements of $ U $.

For each query, output one integer per line representing the answer modulo $ 998244353 $.

**Sample 1 Explanation** The prefix is `abc` (encoded as `1 2 3`), $ U = \{a\} $, and the character set is $\{a,b,c,d,e\}$. The valid strings of length 5 are: ```plain abcda abcea ``` Hence the answer is 2. **Sample 2 Explanation** The prefix is `abc`, $ U = \{a,b\} $. Among valid strings of length 7, exactly 6 meet the conditions. ```plain abceadb abcdeab abcedba abcdeba abcedab abcdaeb ``` Hence the answer is 6. **Constraints** For all test cases: $1 \leq n \leq 10^7$，$1 \leq q,m \leq 2 \times 10^3$，$m + 3 \leq k\le 10^9$，$U \subseteq [1,k]$，$T_i \in [1,k]$。 | Subtask | $ q = $ | $ n \leq $ | $ m = $ | $ \sum \vert U \vert = $ | Additional Constraints | |:-:|:-:|:-:|:-:|:-:|:-:| | 1 | $700$ | $700$ | $100$ | $700$ | $ k-m=3 $ | | 2 | $700$ | $700$ | $100$ | $700$ | None | | 3 | $ 10^3 $ | $ 5 \times 10^5 $ | $20$ | $ 4 \times 10^3 $ | None | | 4 | $ 2 \times 10^3 $ | $ 5 \times 10^5 $ | $100$ | $ 4 \times 10^3 $ | None | | 5 | $ 2 \times 10^3 $ | $ 5 \times 10^5 $ | $100$ | $ 10^6 $ | None | | 6 | $ 2 \times 10^3 $ | $ 2.5 \times 10^5 $ | $ 10^3 $ | $ 4 \times 10^3 $ | None | | 7 | $ 2 \times 10^3 $ | $ 5 \times 10^5 $ | $ 2 \times 10^3 $ | $ 4 \times 10^3 $ | None | | 8 | $ 2 \times 10^3 $ | $ 2.5 \times 10^5 $ | $ 10^3 $ | $ 10^6 $ | None | | 9 | $ 2 \times 10^3 $ | $ 5 \times 10^5 $ | $ 2 \times 10^3 $ | $ 10^6 $ | None | | 10 | $ 2 \times 10^3 $ | $10^7 $ | $ 2 \times 10^3 $ | $ 2 \times 10^6 $ | None |