【数位dp】hdu4389
X mod f(x)
Problem Description
Here is a function f(x):
int f ( int x ) {
if ( x == 0 ) return 0;
return f ( x / 10 ) + x % 10;
}
Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10 9), how many integer x that mod f(x) equal to 0. Input
The first line has an integer T (1 <= T <= 50), indicate the number of test cases.
Each test case has two integers A, B.
Each test case has two integers A, B.
Output
For each test case, output only one line containing the case number and an integer indicated the number of x.
Sample Input
2 1 10 11 20
Sample Output
Case 1: 10 Case 2: 3 我看到网上好多题解都是部分打表，作为一个曾经的oi党，表示感动得泪流满面啊！ 其实和之前那道求13的倍数有点像， 由于f（x）最大就是81，所以可以算对于1 - 81每一个数都求一下 f[pos][mod][x][sum] 表示前pos位数，除以x的余数是mod，各个位数和为sum的数的个数 其他的见代码…… 今天最开始没有初始化f数组，样例死活过不了，检查了半个多小时，orz，脑抽
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stdlib.h>
using namespace std;
int f[11][82][82][82];
int bit[11];
int dp(int pos, int mod, int x, int sum, bool flag)
{
if (pos == 0) return (x == sum && mod % sum == 0);
if(flag && f[pos][mod][x][sum] != -1)return f[pos][mod][x][sum];
int re = 0;
int d = flag ? 9 : bit[pos];
for (int i = 0; i <= d; i++)
{
int tmp = (mod * 10 + i) % x;
re += dp(pos - 1, tmp , x, sum + i ,flag || i < d);
}
if (flag) f[pos][mod][x][sum] = re;
return re;
}
int calc(int x)
{
int len = 0;
while(x)
{
bit[++len] = x % 10;
x /= 10;
}
int sum = 0;
for (int i = 1; i <= 81; i++)
{
sum += dp(len, 0, i, 0, 0);
}
return sum;
}
int main()
{
int t, l , r;
memset(f, -1, sizeof(f));
scanf("%d", &t);
for (int i = 1; i <= t; i++)
{
scanf("%d%d", &l, &r);
printf("Case %d: %d\n", i, calc(r) - calc(l - 1));
}
return 0;
}
查看11道真题和解析