hdu4389

maksyuki 发表于 oj 分类，标签: DP-数位DP

05 12月 2015

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⁹), 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.

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

Author

WHU

Source

2012 Multi-University Training Contest 9

题目类型：数位DP

算法分析：dp[pos][mod][d][sum]表示前i位数除以d得到余数mod且此时前i位和为sum的数字的个数，这里d在1~81范围内枚举，递归的边界是恰好满足d == sum且mod % sum == 0，最后累加所有的情况即可(枚举d)

/*************************************************
Author        :supermaker
Created Time  :2015/12/4 23:45:43
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int dp[12][83][83][83], bit[66];

int SS (int pos, int mod, int d, int sum, bool flag)
{
	if (pos == 0) return (d == sum && mod % sum == 0);
	if (flag && dp[pos][mod][d][sum] != -1) return dp[pos][mod][d][sum];
	
	int res = 0;
	int x = flag ? 9 : bit[pos];
	for (int i = 0; i <= x; i++)
	{
		int tt = (mod * 10 + i) % d;
		res += SS (pos - 1, tt, d, sum + i, flag || i < x);
	}
	return flag ? dp[pos][mod][d][sum] = res : res;
}

int Calc (int val)
{
	int len = 0;
	while (val)
	{
		bit[++len] = val % 10;
		val /= 10;
	}
	
	int res = 0;
	for (int i = 1; i <= 81; i++)
		res += SS (len, 0, i, 0, 0);
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	memset (dp, -1, sizeof (dp));
	int t, id = 1;
	scanf ("%d", &t);
	while (t--)
	{
		int vala, valb;
		scanf ("%d%d", &vala, &valb);
		printf ("Case %d: %d\n", id++, Calc (valb) - Calc (vala - 1));
	}
    return 0;
}

100

101

102

/*************************************************

Author :supermaker

Created Time :2015/12/4 23:45:43

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int dp[12][83][83][83], bit[66];

int SS (int pos, int mod, int d, int sum, bool flag)

{

if (pos == 0) return (d == sum && mod % sum == 0);

if (flag && dp[pos][mod][d][sum] != -1) return dp[pos][mod][d][sum];

int res = 0;

int x = flag ? 9 : bit[pos];

for (int i = 0; i <= x; i++)

{

int tt = (mod * 10 + i) % d;

res += SS (pos - 1, tt, d, sum + i, flag || i < x);

}

return flag ? dp[pos][mod][d][sum] = res : res;

}

int Calc (int val)

{

int len = 0;

while (val)

{

bit[++len] = val % 10;

val /= 10;

}

int res = 0;

for (int i = 1; i <= 81; i++)

res += SS (len, 0, i, 0, 0);

return res;

}

int main()

{

//CFF;

//CPPFF;

memset (dp, -1, sizeof (dp));

int t, id = 1;

scanf ("%d", &t);

while (t--)

{

int vala, valb;

scanf ("%d%d", &vala, &valb);

printf ("Case %d: %d\n", id++, Calc (valb) - Calc (vala - 1));

}

return 0;

}

hdu3652

codeforces 55D

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

hdu4389

X mod f(x)

分类目录

标签云

书签

近期评论