Vlad and the Nice Paths (easy version) (Codeforces 1811G1)
Tags: Math, combinatorics

This is an easy version of the problem, it differs from the hard one only by constraints on $$$n$$$ and $$$k$$$.Vlad found a row of $$$n$$$ tiles and the integer $$$k$$$. The tiles are indexed from left to right and the $$$i$$$-th tile has the color $$$c_i$$$. After a little thought, he decided what to do with it.You can start from any tile and jump to any number of tiles right, forming the path $$$p$$$. Let's call the path $$$p$$$ of length $$$m$$$ nice if:  $$$p$$$ can be divided into blocks of length exactly $$$k$$$, that is, $$$m$$$ is divisible by $$$k$$$;  $$$c_{p_1} = c_{p_2} = \ldots = c_{p_k}$$$;  $$$c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$$$;  $$$\ldots$$$  $$$c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$$$; Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

Input: The first line of each test contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of tiles in a row and the length of the block.The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — tile colors.It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$5 \cdot 10^6$$$.

Output: Print $$$t$$$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $$$10^9 + 7$$$.

Note: In the first sample, it is impossible to make a nice path with a length greater than $$$0$$$.In the second sample, we are interested in the following paths:  $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$  $$$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$$$  $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$  $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$ In the third example, any path of length $$$8$$$ is nice.

Sample Inputs:
5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5

Sample Outputs:
1
4
165
3
1

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    bigg = 0
    for j in range(len(a)):
        if bigg < a[j]:
            bigg = a[j]
    ans = [1] * n
    maxx = [0] * n
    dp = [0] * (bigg + 1) * n
    counter = [0] * (bigg + 1)
    if k == 1:
        print(1)
    else:
        for j in range(n):
            spam = 0
            dp[a[j] * n + counter[a[j]]] = j
            counter[a[j]] = counter[a[j]] + 1
            if counter[a[j]] < k and j != 0:
                ans[j] = ans[j - 1]
                maxx[j] = maxx[j - 1]
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] > maxx[j - 1] - k):
                food = maxx[dp[a[j] * n + counter[a[j]] - k] - 1]
                for m in range(counter[a[j]] - k + 1):
                    if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] == food:
                        spam = spam + 1
                comba = 1
                g_1 = 1
                g_2 = k + 1
                ans[j] = 0
                for m in range(spam):
                    ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1] * comba
                    comba = g_2 - g_1
                    g_2 = g_2 * (k + m + 2) // (m + 2)
                maxx[j] = maxx[dp[a[j] * n + counter[a[j]] - k] - 1] + k
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] == maxx[j - 1] - k):
                food = maxx[dp[a[j] * n + counter[a[j]] - k] - 1]
                for m in range(counter[a[j]] - k + 1):
                    if dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] == food:
                            spam = spam + 1
                    if dp[a[j] * n + counter[a[j]] - k - m] - 1 == -1:
                        if maxx[0] == food:
                            spam = spam + 1
                comba = k - 1
                g_1 = k
                g_2 = k * (k + 1) // 2
                ans[j] = ans[j - 1]
                for m in range(spam):
                    if m == 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1]
                    if m == 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 < 0:
                        ans[j] = ans[0]
                    if m != 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1] * comba
                        comba = g_2 - g_1
                        g_1 = g_2
                        g_2 = g_2 * (k + m + 1) // (m + 2)
                    if m != 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 < 0:
                        ans[j] = ans[j] + ans[0] * comba
                        comba = g_2 - g_1
                        g_1 = g_2
                        g_2 = g_2 * (k + m + 1) // (m + 2)
                    maxx[j] = maxx[j - 1]
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 < 0:
                if maxx[0] < maxx[j - 1] - k:
                    ans[j] = ans[j - 1]
                    maxx[j] = maxx[j - 1]
                if maxx[0] > maxx[j - 1] - k:
                    ans[j] = 1
                    maxx[j] = k
                if maxx[0] == maxx[j - 1] - k:
                    ans[j] = ans[j - 1] + 1
                    maxx[j] = k
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] < maxx[j - 1] - k):
                ans[j] = ans[j - 1]
                maxx[j] = maxx[j - 1]
        print(ans[n - 1] % (10 ** 9 + 7))

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    bigg = 0
    for j in range(len(a)):
        if bigg < a[j]:
            bigg = a[j]
    ans = [1] * n
    maxx = [0] * n
    dp = [0] * (bigg + 1) * n
    counter = [0] * (bigg + 1)
    if k == 1:
        print(1)
    else:
        for j in range(n):
            spam = 0
            dp[a[j] * n + counter[a[j]]] = j
            counter[a[j]] = counter[a[j]] + 1
            if counter[a[j]] < k and j != 0:
                ans[j] = ans[j - 1]
                maxx[j] = maxx[j - 1]
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] > maxx[j - 1] - k):
                food = maxx[dp[a[j] * n + counter[a[j]] - k] - 1]
                for m in range(counter[a[j]] - k + 1):
                    if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] == food:
                        spam = spam + 1
                    if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] != food:
                        break
                comba = 1
                g_1 = 1
                g_2 = k + 1
                ans[j] = 0
                for m in range(spam):
                    ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1] * comba
                    comba = g_2 - g_1
                    g_2 = g_2 * (k + m + 2) // (m + 2)
                maxx[j] = maxx[dp[a[j] * n + counter[a[j]] - k] - 1] + k
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] == maxx[j - 1] - k):
                food = maxx[dp[a[j] * n + counter[a[j]] - k] - 1]
                for m in range(counter[a[j]] - k + 1):
                    if dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] == food:
                            spam = spam + 1
                        if maxx[dp[a[j] * n + counter[a[j]] - k - m] - 1] != food:
                            break
                    if dp[a[j] * n + counter[a[j]] - k - m] - 1 == -1:
                        if maxx[0] == food:
                            spam = spam + 1
                comba = k - 1
                g_1 = k
                g_2 = k * (k + 1) // 2
                ans[j] = ans[j - 1]
                for m in range(spam):
                    if m == 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1]
                    if m == 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 < 0:
                        ans[j] = ans[0]
                    if m != 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 >= 0:
                        ans[j] = ans[j] + ans[dp[a[j] * n + counter[a[j]] - k - m] - 1] * comba
                        comba = g_2 - g_1
                        g_1 = g_2
                        g_2 = g_2 * (k + m + 1) // (m + 2)
                    if m != 0 and dp[a[j] * n + counter[a[j]] - k - m] - 1 < 0:
                        ans[j] = ans[j] + ans[0] * comba
                        comba = g_2 - g_1
                        g_1 = g_2
                        g_2 = g_2 * (k + m + 1) // (m + 2)
                    maxx[j] = maxx[j - 1]
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 < 0:
                if maxx[0] < maxx[j - 1] - k:
                    ans[j] = ans[j - 1]
                    maxx[j] = maxx[j - 1]
                if maxx[0] > maxx[j - 1] - k:
                    ans[j] = 1
                    maxx[j] = k
                if maxx[0] == maxx[j - 1] - k:
                    ans[j] = ans[j - 1] + 1
                    maxx[j] = k
            elif counter[a[j]] >= k and dp[a[j] * n + counter[a[j]] - k] - 1 >= 0 and (maxx[dp[a[j] * n + counter[a[j]] - k] - 1] < maxx[j - 1] - k):
                ans[j] = ans[j - 1]
                maxx[j] = maxx[j - 1]
        print(ans[n - 1] % (10 ** 9 + 7))

Solution (Python):
M = 10 ** 9 + 7

def pw(a, n):
    if n == 0:
        return 1
    b = pw(a, n // 2)
    return b * b % M * (a if n % 2 == 1 else 1) % M

def obr(x):
    return pw(x, M - 2)

def cnk(n, k):
    return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M

def solve():
    (n, k) = map(int, input().split())
    c = [-1] + [int(x) for x in input().split()]
    if k == 1:
        print(1)
        return
    dp = [[0] * (n // k + 1) for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(0, n // k + 1):
            if j > 0:
                sz = 1
                for s in range(i - 1, -1, -1):
                    if c[s] == c[i]:
                        sz += 1
                        if sz >= k:
                            dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M
                            dp[i][j] %= M
            dp[i][j] += dp[i - 1][j]
            dp[i][j] %= M
    for j in range(n // k, -1, -1):
        if dp[n][j] > 0:
            print(dp[n][j])
            return
fact = [1] * 101
for i in range(1, 101):
    fact[i] = fact[i - 1] * i % M
for i in range(int(input())):
    solve()