HDU 6156 2016ICPC网络赛 G: Palindrome Function(数位DP)
程序员文章站
2022-06-04 15:41:26
...
题意:
已知函数f(x, k),如果10进制数x在k进制下是个回文数,那么f(x, k)值为k,否则为1
现给出l, r, x, y, 求出∑∑f(i, j) (l<=i<=r) (x<=j<=y)
数位DP模板题,可是很容易就超时了
dp[p][len][pos]表示p进制下长度为len,枚举到了pos位的回文数数量
#include<stdio.h>
#include<string.h>
#define LL long long
int p, str[38], temp[38];
LL dp[38][32][32];
int Read()
{
int x = 0, f = 1;
char ch;
ch = getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-') f = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
x = x*10+ch-'0', ch = getchar();
return x*f;
}
LL Sech(int len, int pos, int flag, int k)
{
int u, i;
LL ans;
if(pos<0)
return 1;
if(flag==0 && k==0 && dp[p][len][pos]!=-1)
return dp[p][len][pos];
if(flag==1) u = str[pos];
else u = p-1;
ans = 0;
for(i=0;i<=u;i++)
{
temp[pos] = i;
if(k==1)
ans += Sech(len-(k && i==0), pos-1, flag && i==u, i==0);
else if(pos<(len+1)/2 && i==temp[len-pos] || pos>=(len+1)/2)
ans += Sech(len, pos-1, flag && i==u, 0);
}
if(flag==0 && k==0)
dp[p][len][pos] = ans;
return ans;
}
LL Jud(int x)
{
int len;
len = 0;
while(x)
{
str[len++] = x%p;
x /= p;
}
return Sech(len-1, len-1, 1, 1);
}
int main(void)
{
int T, l, r, i, x, y, cas = 1;
LL ans;
scanf("%d", &T);
memset(dp, -1, sizeof(dp));
while(T--)
{
ans = 0;
l = Read(), r = Read();
x = Read(), y = Read();
for(i=x;i<=y;i++)
{
p = i;
ans += (Jud(r)-Jud(l-1))*(i-1);
}
printf("Case #%d: %lld\n", cas++, ans+(LL)(r-l+1)*(y-x+1));
}
}