PROGRAMMING:Poor complexity
Unfortunately, there is an array $$a $. The complexity of its definition $$C (a) $$is equal to the number of its essentially different subintervals. For example, $$C ([1,1,1]) = 3 $$, because $$[1,1,1] $$has only $$3 $$essentially different subintervals $$[1] $, $[1,1] $$and $$[1,1] $; And $$C ([1,2,1]) = 5 $$, which contains $$5 $$subintervals of different nature - $[1] $, $[2] $, $[1,2] $, $[2,1] $, $[1,2,1] $.
I'm going to come up with a topic about complexity. As we all know, the introduction of randomness can often transform a simple topic. Now, I have an array of positive integers of length $$n $$$$and a positive integer $$M $$. Next, we randomly generate the random integer $$Y in $$n $$[1, M] $_ I $$, and put $$X_ I $$is changed to $$MX_ i+y_ i$$。
Obviously, there are $$n = m ^ n $$possible result arrays. Now, I want you to find the sum of the complexity of these $$n $$arrays.
###Input format:
The first line gives an integer $$t $$($$1 / le t / Le 5 $$) to represent the number of data groups.
For each set of data, enter two integers $$n $$and $$M $$($$1 / Le n / Le 100, 1 / Le M / Le 10 ^ 9 $$) in the first line, and the second line is an integer separated by $$n $$spaces to represent the initial value of the array $$x $($$1 / Le x)_ i \le 10^9$$)。
###Output format:
For each group of data, output a line of an integer to represent the answer. The answer may be very big. You only need to output the result after taking the module of $$998244353 $.
###Input example:
```in
four
3 2
1 1 1
3 2
1 2 1
5 2
1 2 1 2 1
10 2
80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045
```
###Output example:
```out
thirty-six
forty-four
four hundred and four
forty-four thousand six hundred and sixteen
```
answer：If there is no answer, please comment
We use $$x $$to represent the input array, $$y $$to represent the changed array, and $$x [l: R] $$to represent the subarray formed by the interval of $$x $$$[l, R] $.
For two intervals_ 1,r_ 1] $$$and $$[l_ 2,r_ 2] $$, if $$x [l]_ 1:r_ 1] \neq x[l_ 2,r_ 2] $$, then $$y [l]_ 1:r_ 1] $$must not be equal to $$y [l]_ 2:r_ 2]$$。 So we can consider each essentially different subinterval of $$x $$.
For a subarray of length $$k $$, $$Z $$, suppose that it appears $$t $$times at $$x $$, and the left end subscript of this occurrence is $$a from left to right_ 1, \cdots, a_ t$$。 We only need to calculate how many essentially different substrings are contributed by these $$t $$times in the $$n $$possible array, and the final answer is the sum of the contributions of all essentially different substrings.
Consider inclusion and exclusion, for $$a = \ {a}_ 1, \cdots, a_ Every nonempty subset of t \} $$B = \ {B}_ 1, \cdots, b_ W \} $$, we calculate the number of possible $$y $$to make the occurrence of $$W $$the same (denoted as $$C (b) $), then the contribution of subarray $$Z $$to the answer is:
$$
\sum_{ B \subseteq A, |B| > 0} (-1)^{|B| - 1} \times c(B)
$$
Consider how to calculate $$C (b) $. In the case of $$B $$given, every position of $$x $$has two possibilities: to be appeared at a certain time (that is, a $$[b])_ i: b_ I + k-1] $$) is covered or not covered by any one occurrence. For the latter, the value of this position can be arbitrarily selected, and its contribution to the answer is multiplied by $$M $$. So we just need to consider the first case.
For all positions in the first case, if $$y [b]_ 1:b_ If the value of 1 + k-1] $$has been determined, then the values of all the positions in the first case have been determined. But the problem is that there are some $$y [b]_ 1:b_ Illegal value of 1 + k-1] $. For example, $$n = 3, k = 2, B = \ {1,2 \} $$, then the two characters in $$y [1:2] $$must be equal, for example, the string $$y [1:2] $$must not be equal to $$y [2:3] $.
Consider two adjacent occurrences of $$B_ I $$and $$B_{ I + 1} $$, if the two intersect, that is $$B_ i + k -1 \ge b_{ I + 1} $$, then for $$y [b_ 1:b_ 1 + k-1] $$creates a constraint: the length of the string is $$B_ i+k-b_{ The suffix and prefix of I + 1} $$must be equal, that is, there exists a length of $$B_{ i}+k-b_{ I + 1} $. To calculate $$C (b) $, all you need to do is to take into account all the restrictions, which take $$y [b]_ 1:b_ The position of 1 + k-1] $$is divided into several equivalence classes, and the value of each equivalence class can be arbitrarily taken. Therefore, if there are $$I $$equivalence classes, then the number of value schemes of the first position is $$m ^ I $$.
Let the equivalence class be the "state" of a string, $$f (n) $$denotes the number of different states of a string of length $$n $. For example, $$f (3) = 3 $$, they are respectively three positions are not required to be the same, the first position and the third position must be the same, and the three positions must be the same. An interesting conclusion is that the size of $$f (n) $$is not very large: $$f (50) = 2249, f (100) = 35200 $$. So we can consider dividing the current equivalence class into the state of indentation dynamic programming.
Let's consider adding the elements in $$a $$to $$B $$from left to right. Let $$g [i] [J] [S] $$indicate that $$a is considered_ I $$and put $$a_ If I $$is added to $$B $, the current size of $$B $$is $$J $, and the status of equivalent class is the contribution when $$s $$, then every time you enumerate the position of $$a in the next addition to $$B $$_ T $$, and then according to $$a_ T $$and $$a_ Update $$s $$according to the overlap between I $$and the overlap length, and transfer the corresponding contribution to $$g [t] [J + 1] [s'] $.
If you write this directly, it may time out. You need to use two tricks to optimize it
1. We don't care about the size of $$B $, we only care about the parity of the size of $$B $, so we only need to record the parity of the size in the state.
2. When $$k $$is large, some states are not reachable: the longest overlap length is only $$n-k $$. Eliminating all unreachable equivalent states can speed up the process.
I'm going to come up with a topic about complexity. As we all know, the introduction of randomness can often transform a simple topic. Now, I have an array of positive integers of length $$n $$$$and a positive integer $$M $$. Next, we randomly generate the random integer $$Y in $$n $$[1, M] $_ I $$, and put $$X_ I $$is changed to $$MX_ i+y_ i$$。
Obviously, there are $$n = m ^ n $$possible result arrays. Now, I want you to find the sum of the complexity of these $$n $$arrays.
###Input format:
The first line gives an integer $$t $$($$1 / le t / Le 5 $$) to represent the number of data groups.
For each set of data, enter two integers $$n $$and $$M $$($$1 / Le n / Le 100, 1 / Le M / Le 10 ^ 9 $$) in the first line, and the second line is an integer separated by $$n $$spaces to represent the initial value of the array $$x $($$1 / Le x)_ i \le 10^9$$)。
###Output format:
For each group of data, output a line of an integer to represent the answer. The answer may be very big. You only need to output the result after taking the module of $$998244353 $.
###Input example:
```in
four
3 2
1 1 1
3 2
1 2 1
5 2
1 2 1 2 1
10 2
80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045
```
###Output example:
```out
thirty-six
forty-four
four hundred and four
forty-four thousand six hundred and sixteen
```
answer：If there is no answer, please comment
We use $$x $$to represent the input array, $$y $$to represent the changed array, and $$x [l: R] $$to represent the subarray formed by the interval of $$x $$$[l, R] $.
For two intervals_ 1,r_ 1] $$$and $$[l_ 2,r_ 2] $$, if $$x [l]_ 1:r_ 1] \neq x[l_ 2,r_ 2] $$, then $$y [l]_ 1:r_ 1] $$must not be equal to $$y [l]_ 2:r_ 2]$$。 So we can consider each essentially different subinterval of $$x $$.
For a subarray of length $$k $$, $$Z $$, suppose that it appears $$t $$times at $$x $$, and the left end subscript of this occurrence is $$a from left to right_ 1, \cdots, a_ t$$。 We only need to calculate how many essentially different substrings are contributed by these $$t $$times in the $$n $$possible array, and the final answer is the sum of the contributions of all essentially different substrings.
Consider inclusion and exclusion, for $$a = \ {a}_ 1, \cdots, a_ Every nonempty subset of t \} $$B = \ {B}_ 1, \cdots, b_ W \} $$, we calculate the number of possible $$y $$to make the occurrence of $$W $$the same (denoted as $$C (b) $), then the contribution of subarray $$Z $$to the answer is:
$$
\sum_{ B \subseteq A, |B| > 0} (-1)^{|B| - 1} \times c(B)
$$
Consider how to calculate $$C (b) $. In the case of $$B $$given, every position of $$x $$has two possibilities: to be appeared at a certain time (that is, a $$[b])_ i: b_ I + k-1] $$) is covered or not covered by any one occurrence. For the latter, the value of this position can be arbitrarily selected, and its contribution to the answer is multiplied by $$M $$. So we just need to consider the first case.
For all positions in the first case, if $$y [b]_ 1:b_ If the value of 1 + k-1] $$has been determined, then the values of all the positions in the first case have been determined. But the problem is that there are some $$y [b]_ 1:b_ Illegal value of 1 + k-1] $. For example, $$n = 3, k = 2, B = \ {1,2 \} $$, then the two characters in $$y [1:2] $$must be equal, for example, the string $$y [1:2] $$must not be equal to $$y [2:3] $.
Consider two adjacent occurrences of $$B_ I $$and $$B_{ I + 1} $$, if the two intersect, that is $$B_ i + k -1 \ge b_{ I + 1} $$, then for $$y [b_ 1:b_ 1 + k-1] $$creates a constraint: the length of the string is $$B_ i+k-b_{ The suffix and prefix of I + 1} $$must be equal, that is, there exists a length of $$B_{ i}+k-b_{ I + 1} $. To calculate $$C (b) $, all you need to do is to take into account all the restrictions, which take $$y [b]_ 1:b_ The position of 1 + k-1] $$is divided into several equivalence classes, and the value of each equivalence class can be arbitrarily taken. Therefore, if there are $$I $$equivalence classes, then the number of value schemes of the first position is $$m ^ I $$.
Let the equivalence class be the "state" of a string, $$f (n) $$denotes the number of different states of a string of length $$n $. For example, $$f (3) = 3 $$, they are respectively three positions are not required to be the same, the first position and the third position must be the same, and the three positions must be the same. An interesting conclusion is that the size of $$f (n) $$is not very large: $$f (50) = 2249, f (100) = 35200 $$. So we can consider dividing the current equivalence class into the state of indentation dynamic programming.
Let's consider adding the elements in $$a $$to $$B $$from left to right. Let $$g [i] [J] [S] $$indicate that $$a is considered_ I $$and put $$a_ If I $$is added to $$B $, the current size of $$B $$is $$J $, and the status of equivalent class is the contribution when $$s $$, then every time you enumerate the position of $$a in the next addition to $$B $$_ T $$, and then according to $$a_ T $$and $$a_ Update $$s $$according to the overlap between I $$and the overlap length, and transfer the corresponding contribution to $$g [t] [J + 1] [s'] $.
If you write this directly, it may time out. You need to use two tricks to optimize it
1. We don't care about the size of $$B $, we only care about the parity of the size of $$B $, so we only need to record the parity of the size in the state.
2. When $$k $$is large, some states are not reachable: the longest overlap length is only $$n-k $$. Eliminating all unreachable equivalent states can speed up the process.