Wojtek and Card Tricks
Contest: Dasha Code Championship - SPb Finals Round (only for onsite-finalists)
Difficulty rating: 2700
Tags: math

Wojtek has just won a maths competition in Byteland! The prize is admirable — a great book called 'Card Tricks for Everyone.' 'Great!' he thought, 'I can finally use this old, dusted deck of cards that's always been lying unused on my desk!'

The first chapter of the book is 'How to Shuffle $$$k$$$ Cards in Any Order You Want.' It's basically a list of $$$n$$$ intricate methods of shuffling the deck of $$$k$$$ cards in a deterministic way. Specifically, the $$$i$$$-th recipe can be described as a permutation $$$(P_{i,1}, P_{i,2}, \dots, P_{i,k})$$$ of integers from $$$1$$$ to $$$k$$$. If we enumerate the cards in the deck from $$$1$$$ to $$$k$$$ from top to bottom, then $$$P_{i,j}$$$ indicates the number of the $$$j$$$-th card from the top of the deck after the shuffle.

The day is short and Wojtek wants to learn only some of the tricks today. He will pick two integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$), and he will memorize each trick from the $$$l$$$-th to the $$$r$$$-th, inclusive. He will then take a sorted deck of $$$k$$$ cards and repeatedly apply random memorized tricks until he gets bored. He still likes maths, so he started wondering: how many different decks can he have after he stops shuffling it?

Wojtek still didn't choose the integers $$$l$$$ and $$$r$$$, but he is still curious. Therefore, he defined $$$f(l, r)$$$ as the number of different decks he can get if he memorizes all the tricks between the $$$l$$$-th and the $$$r$$$-th, inclusive. What is the value of

$$$$$$\sum_{l=1}^n \sum_{r=l}^n f(l, r)?$$$$$$

Input format:
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le k \le 5$$$) — the number of tricks and the number of cards in Wojtek's deck.

Each of the following $$$n$$$ lines describes a single trick and is described by $$$k$$$ distinct integers $$$P_{i,1}, P_{i,2}, \dots, P_{i, k}$$$ ($$$1 \le P_{i, j} \le k$$$).

Output format:
Output the value of the sum described in the statement.

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

Note:
Consider the first sample:

- The first trick swaps two top cards.
- The second trick takes a card from the bottom and puts it on the top of the deck.
- The third trick swaps two bottom cards.

The first or the third trick allow Wojtek to generate only two distinct decks (either the two cards are swapped or not). Therefore, $$$f(1, 1) = f(3, 3) = 2$$$.

The second trick allows him to shuffle the deck in a cyclic order. Therefore, $$$f(2,2)=3$$$.

It turns that two first tricks or two last tricks are enough to shuffle the deck in any way desired by Wojtek. Therefore, $$$f(1,2) = f(2,3) = f(1,3) = 3! = 6$$$.

Example input:
3 3
2 1 3
3 1 2
1 3 2

Example output:
25

Example input:
2 4
4 1 3 2
4 3 1 2

Example output:
31

Editorial:
Let's first enumerate all permutations by integers from $$$0$$$ to $$$k!-1$$$. Now, we can memoize all possible compositions of two permutations in an $$$k! \times k!$$$ array. This will allow us to compose any two permutations in constant time.
Let $$$l$$$ and $$$r$$$ be the left and right ends of any interval. We'll compute the sum in the problem statement for each $$$r$$$ separately. Set some $$$r$$$. Notice that if there are multiple occurrences of the same permutation before $$$r$$$, only the latest occurrence is important for us — any earlier occurrences won't help us create any new decks. Therefore, for each of $$$k!$$$ possible permutations, we can maintain its latest occurrence before $$$r$$$. We can also maintain a sorted list of such latest occurrences among all the permutations — from the latest to the earliest. This creates $$$k!$$$ intervals of value $$$l$$$ where the number of possible decks can't change.
Now, we only need to be able to maintain the set of decks (permutations) we can generate using the tricks we already know. Initially, we can generate only one deck (with the cards in sorted order). When learning a new trick, one of two things can happen:
• If a single application of the new trick generates a deck we can already create using previous tricks, this trick gives us nothing — we can simply simulate this new trick by a sequence of old tricks.
• If this trick $$$T$$$ creates a brand-new deck of cards, we need to recalculate the set of achievable permutations. We maintain a set of generators $$$\{g_1, g_2, \dots, g_a\}$$$, $$$g_a = T$$$ (these are the tricks that have increased the number of decks we can generate). Now, each deck in the new set of decks can be created using this repeatedly applying the generators from this set. We can use BFS/DFS to compute the new decks.
This is obviously a correct algorithm, but why does it work fast enough? If you know some abstract algebra, then you can notice that what we're computing here is a chain of subgroups in a symmetric group $$$S_k$$$ (a group of all permutations of $$$k$$$ elements). By Lagrange's theorem, if a group $$$G$$$ is a subgroup of a finite group $$$H$$$, then $$$|H|$$$ is a multiple of $$$|G|$$$. Therefore, each new set of achievable decks is at least twice as large as the previous one. It means that:
• The set of generators is always at most as large as $$$\log_2(k!)$$$,
• The time needed to compute all the subgroups can be bounded by $$$\log_2(k!)$$$ times the sizes of all subgroups in the chain. As the sizes are growing exponentially large, the sum of sizes is at most $$$O(k!)$$$. Therefore, all the additions take at most $$$O(k! \log k)$$$ time.
The time complexity of the intended solution was therefore $$$O((k!)^2 + nk!k)$$$.
The solution can be sped up significantly by computing all possible sets of achievable decks (i.e., all subgroups of $$$S_k$$$) — for $$$k = 5$$$, there are only $$$156$$$ of them. Some preprocessing will then allow us to add a single element to the subgroup in constant time. This was however not necessary to get AC.