Reformulating the Condition

For sequences \(A\) and \(B\), Let \(B\prec A\) denote that \(B\) is a subsequence of \(A\). For a sequence \((x_1,\dots,x_m)\), let \(f((x_1,\dots,x_m))\) be the set of sequences satisfying all conditions from the problem statement except length. That is,

\[ f((x_1,\dots,x_m)) = \{a \in \{1,\dots, K\}^* \mid \forall b \in \{1,\dots, K\}^m ~ b\prec a \iff b\neq (x_1,\dots,x_m)\} \]

Note that elements of \(f((x_1,\dots,x_m))\) contain any sequence of length less than \(m\) as a subsequence.

Case: \(X_1=X_2\)

First, let’s list necessary conditions for \((A_1,\dots,A_N)\in f((X_1,\dots,X_M))\) when \(X_1=X_2\).

Let \(i\) be the position of the first occurrence of \(X_1\) in \((A_1,\dots,A_N)\) (if none exists, the conditions aren’t satisfied). Then we need:

1. \((A_{i+1},\dots,A_N)\in f((X_2,\dots,X_M))\)
2. All numbers except \(X_1\) appear in \(A_1,\dots,A_{i-1}\)

To verify necessity of 2, consider the case where there exists a number \(s\) whose first occurrence is later than that of \(X_1\). Let \(j\) be its first position (\(i<j\)). From 1, \((X_2,\dots,X_M) \nprec (A_{i+1},\dots,A_{j+1},\dots,A_N)\), so clearly \((X_2,\dots,X_M) \nprec (A_{j+1},\dots,A_N)\), which means \((s,X_2,\dots,X_M) \nprec (A_1,\dots,A_N)\).

Let’s verify that these two conditions are also sufficient.

\((X_1,X_2,\dots,X_M) \nprec (A_1,\dots,A_N)\) follows directly from 1. Similarly, for \((X'_2,\dots,X'_M)\neq(X_2,\dots,X_M)\), it follows from 1 that \((X_1,X'_2,\dots,X'_M)\prec (A_1,\dots,A_N)\). We now need to show \((X'_1,X_2,\dots,X_M) \prec (A_1,\dots,A_N)\) when \(X'_1\neq X_1\). From 2, \((X'_1,X_2)\prec (A_1,\dots,A_i)\). From 1, since \((X_3,\dots,X_M)\) is of length less than \(M-1\), \((X_3,\dots,X_M)\prec (A_{i+1},\dots,A_N)\). Therefore, \((X'_1,X_2,\dots,X_M) \prec (A_1,\dots,A_N)\).

Case: \(X_1\neq X_2\)

Similarly for \(X_1\neq X_2\), let’s list necessary conditions for \((A_1,\dots,A_N)\in f((X_1,\dots,X_M))\).

Let \(i\) be the position of the first occurrence of \(X_1\). As before, we need:

1. \((A_{i+1},\dots,A_N)\in f((X_2,\dots,X_M))\)

2. All numbers except \(X_1\) appear in \(A_1,\dots,A_{i-1}\)

   Let \(j\) be the position of the last occurrence of \(X_2\) in \((A_1,\dots,A_{i+1})\). We also need:

3. All numbers except \(X_1\) appear in \(A_1,\dots,A_{j-1}\)

To verify necessity of 3, consider the case where \(s \neq X_1\) doesn’t appear in \(A_1,\dots,A_{j-1}\). Let \(k\) be the first position of \(s\), then from 2, \(j<k<i\). From the choice of \(j\), \(X_2\) doesn’t exist in \(A_{k+1},\dots,A_{i}\), so \((s,X_2,\dots,X_M)\prec (A_1,\dots,A_N) \iff (X_2,\dots,X_M)\prec (A_{i+1},\dots,A_N)\), but from 1, we get \((X,X_2,\dots,X_M)\nprec (A_1,\dots,A_N)\).

These three conditions can be verified to be sufficient in a similar way to the previous case.

Dynamic Programming

Let dp[k][n] be the number of sequences of length \(n\) that are elements of \(f((X_k,\dots,X_M))\). Because condition 1 exists in both cases above, we can update the table as dp[k][n+i] += hoge * dp[k+1][n] for \(k,n,i\). Let’s determine this coefficient hoge.

Case: \(X_k=X_{k+1}\)

From the necessary and sufficient conditions above, the coefficient is the number of sequences of length \(i-1\) that use exactly \(K-1\) different numbers. This can be calculated using the inclusion-exclusion principle in \(O(K)\) for each \(i\), so we need \(O(NK)\) preprocessing.

Case: \(X_k\neq X_{k+1}\)

Organizing the necessary and sufficient conditions:

• First \(j-1\) terms contain exactly \(K-1\) different numbers
• Term \(j\) is \(X_{k+1}\)
• Terms \(j+1\) through \(i-1\) can be any numbers except \(X_k,X_{k+1}\)
• Term \(t\) is \(X_i\)

Thus, we need to precompute the convolution of the sequence calculated in the \(X_k=X_{k+1}\) case with the sequence \(((K-2)^0, (K-2)^1, \dots,)\), which can be done in \(O(N^2)\).

The overall complexity is \(O(N^2M + NK)\), which is fast enough.

Sample Implementation in C++