P5040题解

Feyn · 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];//做好记忆化 
}