[题解] CF855E Salazar Slytherin's Locket

Alex_Eon · 2023-06-12 22:47:26 · 题解

博客内食用效果更佳

思路：数位 DP

本题是一道较为基础的数位 DP，不同数字最多有 10 个，所以用二进制状压表示当前情况：若数字 i 出现次数为偶数，则对应的二进制下的第 i+1 位（即 2^i 的位置）用 0 表示，反之则 1。

我们设以下参数进行 DP:

不同的是，本题多测，所以 DP 所用的 f 数组要多开一个维度表示 b 进制下的结果，方便记忆化。

代码实现需要注意的地方：

• 前导零不计入计算。
• 若不达到上限，则当前最大搜索数字为 b-1（b 为进制数）。
• 若超时可以尝试检查记忆化部分。

参考代码：

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=100;

LL l,r,b;
//--------------------//
int num[N];
LL f[N][5000][20];//第二维是状态，第三位是进制

LL DFS(int now,bool lim,bool ze,int sta)
{
    if(now==0)
        return sta==0;//只有全出现偶数次才对答案产生贡献
    if(!lim&&!ze&&f[now][sta][b]!=-1)//记忆化
        return f[now][sta][b];
    int lst=lim?num[now]:b-1;//注意上限取值
    LL res=0;
    for(int i=0;i<=lst;i++)
        res+=DFS(now-1,lim&&i==lst,ze&&i==0,(ze&&i==0)?sta:(sta^(1<<i)));//状态转移
    if(!lim&&!ze)
        f[now][sta][b]=res;
    return res;
}

LL solve(LL x)
{
    int len=0;
    while(x)
    {
        num[++len]=x%b;
        x/=b;
    }
    return DFS(len,true,true,0);
}
//--------------------//
int main()
{   
    int T;
    scanf("%d",&T);
    memset(f,-1,sizeof(f));
    while(T--)
    {
        scanf("%lld%lld%lld",&b,&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}