## Digit Sum

Quy hoạch động chữ số <=> QHD sinh một chuỗi các chữ số (thập phân, nhị phân, ...).

Gọi $dp[i][r][ok]$ là số lượng cách sinh $i$ chữ số đầu tiên và tổng chữ số chia cho $D$ dư $r$, $ok = 0$ nếu các chữ số khớp với $i$ chữ số đầu tiên của $K$, $ok = 1$ nếu như các chữ số có thứ tự từ điển nhỏ hơn $i$ cs đầu của $K$.

$$
dp[i][r][ok] \to dp[i+1][(r+x)\%D][y]
$$
Trong đó:
- $x$ là chữ số thứ $i+1$. Nếu $ok = 0$ thì $x \leq$ chữ số thứ $i+1$ của $K$, ngược lại thì $x \in [0, 9]$.
- $y$ là 0 nếu ok là 0 và x = chữ số thứ i+1 của $K$. Ngược lại, $y = 1$.

## Grouping
Gọi $dp[mask]$ là số cách chia nhóm cho tập $mask$ các con thỏ. Ta tiến hành chuyển trạng thái bằng cách xét các tập con của $mask$.
$$
dp[mask] = \sum\limits_{submask \subset mask} cost(submask) + dp[mask/submask]
$$

Nếu ta tìm submask bằng cách duyệt $2^N$ tập hợp rồi kiểm tra có phải tập con của $mask$ không thì thuật toán có độ phức tạp $O(4^N) \approx 4 \times 10^9$ không đủ tốt để AC bài toán.

Để tối ưu việc duyệt $submask$, ta dùng kĩ thuật được nêu ở:
https://codeforces.com/blog/entry/45223

for(int mask = 0; mask < (1ll<<n); ++mask) {
    for(int sub = mask; sub > 0; sub = (sub-1)&mask) {
         //    
    }
}

Khi đó, độ phức tạp của kĩ thuật này chỉ là $O(3^N)$.

Để tính $cost(submask)$. Ta chuẩn bị trước trong $O(2^N \times N^2)$.

## Walk
Gọi $dp[i][j][cnt]$ là số đường đi từ $i$ đến $j$ qua $cnt$ cạnh. Ta có công thức qhd:
$$
dp[i][j][cnt] = \sum\limits_{x \in [1, n]} dp[i][x][cnt-1] * c[x][j].
$$

Ta có thể dễ dàng giải quyết bài toán với đpt là $O(N^2 K)$.

Tuy nhiên, $K$ quá to, ta cần đi tối ưu chi phí chuyển.

### Lí thuyết ma trận
https://codeforces.com/blog/entry/67776

Xét ma trận $A$ $m \times n$, và ma trận $B$ kích thước $n \times p$. Định nghĩa phép nhân ma trận $AB$ như sau:

$$
AB_{(ij)} = \sum\limits_{1 \le k \le n} A_{i, k} \times B_{k, j}
$$

Ma trận đơn vị là một ma trận $0$ với các số $1$ nằm dọc theo đường chéo chính.

$$
\begin{bmatrix}
1 & 0 & 0 & \dots & 0 \\
0 & 1 & 0 & \dots & 0 \\
0 & 0 & 1 & \dots & 0 \\
\vdots & \vdots & \vdots & & \vdots \\
0 & 0 & 0 & \dots & 1
\end{bmatrix}
$$

## Lời giải





Nhận xét:
Ma trận $DP_{k} = C^k$. Ta thực hiện phép tính lũy thừa trong $O(\log n)$ đối với ma trận $C$ đề cho.

Code: https://ideone.com/JD3EYL

## Permutation

Code: https://ideone.com/5VLtBH