P5040 [SCOI2006] Mapping of Sets in Base $K$

Let $A(N,K)$ be the set of all $N$-digit base-$K$ integers $a$ (the most significant digit of $a$ may be $0$; for example, $0023$ can be regarded as a $4$-digit base-$8$ number or a $4$-digit base-$5$ number. Under the conditions specified in the problem, it can be uniquely determined), where $2 \le K \le 6000$ and $N = 2, 3, 4$. That is, $$A(N,K)={a|a=a_1a_2a_3\cdots a_N,0≤a_i≤K-1,i=1,\cdots,N}$$ Let $D(N-1,K)$ be a subset of $A(N-1,K)$. It is the set of $(N-1)$-digit base-$K$ integers $d$ generated from $A(N,K)$. **The generation rule is as follows**: For any $d \in D(N-1,K)$, there exists $a \in A(N,K)$ such that $d = Image(a)$, where $d = d_1d_2\cdots d_{N-1}$ and $d_i = min(a_i,a_{i+1})$. That is, $d_i$ is the smaller one of $a_i$ and $a_{i+1}$. Note 1: We call this rule a mapping from $A(N,K)$ to $A(N-1,K)$, written as $d = Image(a)$. It can be proven that this mapping is many-to-one. That is, if $d,e \in D(N-1,k)$ and $d \not= e$, then for any elements $a,c \in A(N,K)$ satisfying $d = Image(a)$ and $e = Image(c)$, we have $a \not= c$. Note 2: For some $K,N$, $D(N-1,K)$ is a proper subset of $A(N-1,K)$. For example, when $K=4,N=4$, there does not exist any $a \in A(4,4)$ such that $Image(a)=(323)$. **Task**: Read two integers $N,K$ separated by a space from the input text file, and then output the value of the following expression to the specified output text file: $$f(N,K)=\sum_{a\in A(N,K),Image(a)=d}(\prod_{i=1}^{N-1}(d_i+1))$$ The expression above means: for all elements $a$ in $A(N,K)$, let its image be $d = Image(a) = d_1d_2\cdots d_{N-1}$, add $1$ to each digit of $d$, take the product, and then sum these products. Where $$\prod^{N-1}_{i=1}(d_i+1)=(d_1+1)(d_2+1)\cdots(d_{N-1}+1)$$ **Example**: Let $N=2,K=3$. Then $A(N,K)={00,01,02,11,10,12,20,21,22}$, and the correct output should be $14$. **Hint**: You should first build a suitable method for computation. Directly computing using the expression of $f(N,K)$ will cause most testdata to time out.

The input file contains only one line: two integers $N$ and $K$ separated by a space.

Output a single big integer, which is the computed result.

**About the tests**: Full marks are given if the number is completely correct. When the number of digits of the output exceeds $15$, if only the last two digits are incorrect, half of the score is given. (Each required result does not exceed $10^{19}$.) Translated by ChatGPT 5