数位dp/记忆化搜索

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

一、引例

#1033 : 交错和
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0, a1, ..., an - 1，定义交错和函数：

f(x) = a0 - a1 + a2 - ... + ( - 1)n - 1an - 1

例如：

f(3214567) = 3 - 2 + 1 - 4 + 5 - 6 + 7 = 4

给定 l, r, k，求在 [l, r] 区间中，所有 f(x) = k 的 x 的和，即：

1405402477702.png

输入
输入数据仅一行包含三个整数，l, r, k(0 ≤ l ≤ r ≤ 1018, |k| ≤ 100)。

输出
输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 109 + 7。

提示
对于样例，满足条件的数有 110 和 121，所以结果是 231 = 110 + 121。

/*
************************************交错和***********************************************
******************************by JA/C++ 2015-1-19****************************************
*/ #include <cstdio>
#include <cstring>
long long mod = ;
long long base[];
long long l, r, k, bit[], bt, yy;
struct node {
long long s, n;//s代表数字和，n代表数字个数
};
node dp[][];//状态转移
node dfs(long long pos, long long target, long long limit)//数位dp，基本可以算是模板啦
{
node t;
t.s = t.n = ;
if (pos == ) { //处理到最后一位，直接判断返回
if (target == )
t.n = ;
return t;
}
if ((limit == ) && (dp[pos][target].n != -)) return dp[pos][target];
long long tail = limit ? bit[pos] : ;
long long sgn = ((yy - pos) % ) ? (-) : ();//确定符号
long long head;
if (pos == yy)head = ;
else head = ;//确定搜索的起点和终点
for (long long i= head; i <= tail; i++)
{
node tmp = dfs(pos - , target - i*sgn, (limit == ) && (i == bit[pos]));
if ((tmp.n)>){
t.n += tmp.n;
long long q;
q = ((((tmp.n%mod)*base[pos]) % mod)*i) % mod;//结果的同余处理
t.s += (tmp.s) % mod;
t.s %= mod;
t.s += q;
t.s %= mod;//每一步都要同余
}
}
if (limit == ) dp[pos][target] = t;
return t;
}
long long cal(long long x, long long y)
{
long long ans = ;
if (x == -) return ;
if (x == ) return ;
bt = ;
while (x)
{
bt++;
bit[bt] = x % ;
x /= ;
}
for (yy = ; yy <= bt; yy++){
memset(dp, -, sizeof dp);
ans += dfs(yy, y + , yy == bt).s;//对于每个长度为yy的数字进行处理
ans = (ans + mod) % mod;
}
return ans;
}
int main()
{
base[] = ;
for (int i = ; i <= ; i++)
base[i] = (base[i - ] * ) % mod;
scanf("%lld%lld%lld", &l, &r, &k);
//scanf_s("%lld%lld%lld", &l, &r, &k);
{
printf("%lld", (cal(r, k) - cal(l - , k) + mod) % mod);
}
return ;
}

二、思路分析

给定取值范围，要求区间内数的交错和为给定数，需要用到数位dp,记忆搜索以及同余定理。

1.记忆化搜索写的时候要将相同交错和的个数，相同交错和的数字和分别进行dp。

2.对于一位数字和两位数字的计算方式并不相同，要分数字的位数进行讨论。

3.由于结果可能比较大，每一步都需要使用同余定理。

三、数位dp模板

const int MAX_DIGITS, MAX_STATUS;
LL f[MAX_DIGITS][MAX_STATUS], bits[MAX_DIGITS]; LL dfs(int position, int status, bool limit, bool first)
{
if (position == -)
return s == target_status;
if (!limit && !first && ~f[position][status])
return f[position][status];
int u = limit ? bits[position] : MAX_BITS;
LL ret = ;
for (int i = ; i <= u; i++)
{
ret += dfs(position - , next_status(status, i), limit && i == u, first && !i);
}
return limit || first ? ret : f[pos][status] = ret;
} LL calc(LL n)
{
CLR(f, -);
int len = ;
while (n)
{
bits[len++] = n % ;
n /= ;
}
return dfs(len - , , true, true);
} int main()
{
//freopen("0.txt", "r", stdin);
LL a, b;
while (cin >> a >> b)
cout << calc(b) - calc(a - ) << endl;
return ;
}