#P5040. [SCOI2006] k进制集合的映射

[SCOI2006] k进制集合的映射

题目描述

A(N,K)A(N,K)是全体NNKK进制整数aa的集合(aa的高位可以为00,例如,00230023可看作一个4488进制数,或一个4455进制数,由题中指定的条件可以唯一确定),其中2K60002≤K≤6000N=2N=23344,即:$$A(N,K)={a|a=a_1a_2a_3\cdots a_N,0≤a_i≤K-1,i=1,\cdots,N}$$

D(N1,K)D(N-1,K)A(N1,K)A(N-1,K)的一个子集,它是由A(N,K)A(N,K)生成的一个N1N-1KK进制整数dd的集合,生成规则如下:

对任何dD(N1,K)d\in D(N-1,K),存在aA(N,K)a\in A(N,K),使d=Image(a)d=Image(a),其中,d=d1d2dN1,di=min(ai,ai+1)d=d_1d_2\cdots d_{N-1},d_i=min(a_i,a_{i+1}),即did_i取为ai,ai+1a_i,a_{i+1}的最小值。

注1:我们称这个规则为A(N,K)A(N,K)A(N1,K)A(N-1,K)内的一个映射d=Image(a)d=Image(a),可以证明这个映射是多对一的,即:如果d,eD(N1,k)d,e\in D(N-1,k)ded\not=e,则对任何满足d=Image(a),e=Image(c)d=Image(a),e=Image(c)A(N,K)A(N,K)中的元素a,ca,c,均有aca\not=c

注2:对某些K,NK,N, D(N1,K)D(N-1,K)A(N1,K)A(N-1,K)的一个真子集,例如K=4,N=4K=4,N=4,则不存在aA(4,4)a\in A(4,4),使Image(a)=(323)Image(a)=(323)

任务:从文本文件输入两个用空格隔开的整数 N,KN,K,然后在指定的文本文件中输出下列表达式的值:

$$f(N,K)=\sum_{a\in A(N,K),Image(a)=d}(\prod_{i=1}^{N-1}(d_i+1)) $$

上式表示对A(N,K)A(N,K)中的全部元素aa,对其映像d=Image(a)=d1d2dN1d=Image(a)=d_1d_2\cdots d_{N-1}的各位数字加11后的乘积求和。

其中$\prod^{N-1}_{i=1}(d_i+1)=(d_1+1)(d_2+1)\cdots(d_{N-1}+1)$

:设N=2,K=3N=2,K=3,则A(N,K)=00,01,02,11,10,12,20,21,22A(N,K)={00,01,02,11,10,12,20,21,22},正确的输出结果应为1414

提示:应先建立相应的计算方法,直接利用f(N,K)f(N,K)的表达式计算会使多数测试超时。

输入格式

输入文件只有一行:用空格隔开的两个整数N k。

输出格式

输出文件只有一个大整数,为计算结果。

2  3
14

提示

关于测试的说明

数字完全正确,给满分。当输出结果的位数超过1515位时,如果仅最后两位不准确时给一半分。(每个需测试的计算结果不超过101910^{19})。