HDU 6156 题解
题目分析
设 \(cnt\) 表示在 \(k\) 进制下,\([L,R]\) 范围内回文数的个数。故有 (R-L+1)-cnt
个数字不是回文数。根据题意,在 \(k\) 进制下对答案的贡献为 cnt*k+(R-L+1)-cnt
。
不难想到用数位 DP 去求出 \(cnt\) 的值。
设计状态 \(dp[pos][len][k]\),表示当前填到第 \(pos\) 位,总长度为 \(len\),进制数位 \(k\) 下的数的个数。
Q1 :为何将 \(len\) 设计入状态?
对于 \(k\) 进制下的数 \(x\),必然没有前导零。因此判断它是否为回文数,就看这个长度为 \(len\) 的字符串是否左右对应相等。
Q2 :如何在函数中下传 \(len\) ?
\(len\) 的值与前导零密切相关。如果前面为前导零,且填的这一位仍为 \(0\),那么接下来 dfs 的数的长度就 -1。否则,\(len\) 的值就固定了。
Q3 :如何方便地判断是否为回文串?
- 如果填的为前导零,无需判断,继续搜。
- 如果当前已填的长度小于总长 \(len\) 的一半,则可以任意填 \(0-9\) 间的任意数字,毕竟不影响是否回文。
- 如果当前已填的长度大于总长 \(len\) 的一半,那么填的数就已经固定了,为之前填过的关于 \(\dfrac{len+1}{2}\) 位对称的数字。(\(len\) 为偶数时假想最中间有一位)
Q4 :你怎么知道前面填了什么数?
由于深搜是一条路径往黑里搜,当前所搜的状态之前的东西是暂时不会改变的,因此开一个数组记录当前已填的每位所对应所填入的数字即可。
代码展示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=80;
int k,a[M],c[M];
ll dp[M][M][40];
char s[M];
ll dfs(int pos,int len,int k,bool lead,bool limit)
{
if(pos==0)return 1;
if(!limit&&dp[pos][len][k]!=-1)
return dp[pos][len][k];
int up=limit?a[pos]:k-1;
ll ans=0;
for(int i=0;i<=up;i++)
{
ll tmp=0;c[pos]=i;
if(lead&&(i==0))
tmp=dfs(pos-1,len-1,k,true,limit&&i==up);
else if(pos>len/2)
tmp=dfs(pos-1,len,k,false,limit&&i==up);
else if(c[len-pos+1]==i)
tmp=dfs(pos-1,len,k,false,limit&&i==up);
ans=ans+tmp;
}
if(!limit)dp[pos][len][k]=ans;
return ans;
}
ll solve(ll x,int k)
{
int len=0;
while(x)
{
a[++len]=x%k;
x/=k;
}
return dfs(len,len,k,true,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
int T;scanf("%d",&T);
for(int t=1;t<=T;t++)
{
ll L,R,ans=0;int l,r;
scanf("%lld%lld%d%d",&L,&R,&l,&r);
for(int i=l;i<=r;i++)
{
ll sum=solve(R,i)-solve(L-1,i);
ans+=sum*i;
ans+=(R-L+1-sum);
}
printf("Case #%d: %lld\n",t,ans);
}
return 0;
}