自动搬运

查看原文

来自洛谷，原作者为

	Feyn AFO

搬运于2025-08-24 22:06:28，当前版本为作者最后更新于2022-07-06 12:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

link & 博客园食用

题面很长，而且说得很玄乎，各种专业术语一大堆。但其实它的意思是不难理解的，简单说来，就是给定一个集合 $A$ ，这个集合包含所有位数不超过 $N$ 的 $K$ 进制数（位数不足则补零）。对于一个元素 $a \in A$ ，假如 $a$ 的每一位数字分别是 $a_1,a_2\dots a_N$ ，那么可以构造一个新的长度为 $N-1$ 的序列 $d$ 满足 $\forall i\in[1,N-1],d_i=\min(a_i,a_{i+1})$ 。题目中给这种构造起了一个啥啥映射的名字，并记作 $d=image(a)$ 。同时再定义一种求值的方法，定义序列 $d$ 的价值是 $val(d)=\prod\limits_{i=1}^{|d|}(d_i+1)$ 。题目中求解的东西是 $\sum\limits_{a\in A(N,K)}val(image(a))$ 。

这样一来就比较清晰了。可以想到既然 $A$ 相当于是一个全排列（虽然这么说不严谨），所以 $d$ 每一位上的数字的取值和每个取值的方案数是一样的。还有一个性质不容忽视，假如 $a$ 的前两位已经固定了，那么 $d$ 的第一位也就固定了，那么上面那个求值函数的第一项也就固定了。既然如此我们可以使用小学的时候学过的乘法分配律进行优化，然后做好记忆化，正常转移就可以了。当然正着转移也可以，但我偏向于记忆化搜索。

要写高精度。卡 long long 的都不是什么好东西。

放一下搜索函数的内容：

//node是高精度结构体 
node g[10][N];//记忆化数组 
bool vis[10][N];
node f(int wh,int ch){//当前在填第wh个数，且这个数填的是ch 
	if(wh==m){
		node an=newone;
		an.num=1;an.a[1]=1;
		return an;//到了边界返回1 
	}
	if(vis[wh][ch]==true)return g[wh][ch];//记忆化搜索 
	int an=0;
	for(int i=0;i<n;i++){//枚举那一位可能填的数 
		g[wh][ch]=g[wh][ch]+f(wh+1,i)*(min(ch,i)+1);
		//min(ch,i)+1 相当于是乘法分配律里被提到外面的乘数
		//累加即可 
	}
	vis[wh][ch]=true;
	return g[wh][ch];//做好记忆化 
}