[数据结构与算法]数字游戏

题目描述

由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和?\bmod NmodN?为?00。现在大家又要玩游戏了，指定一个整数闭区间?[a,b][a,b]，问这个区间内有多少个取模数。

输入格式

题目有多组测试数据。每组只含三个数字?a, b, Na,b,N。

输出格式

对于每个测试数据输出一行，表示各位数字和?\bmod NmodN?为?00?的数的个数。

样例

1 19 9

2

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int f[N][10][105],p;
//f[i][j][k]f[i][j][k]代表共i位，最高位为j，且每个位的数之和模N余数为k的数的个数
int mod(int a,int b)
{
	return (a%b+b)%b;
}
void init()
{
	memset(f,0,sizeof f);
	for(int i=0; i<=9; i++) 
			f[1][i][i%p]=1;
	for(int i=2; i<N; i++)
		for(int j=0; j<=9; j++)
			for(int k=0; k<p; k++)
				for(int x=0; x<=9; x++)
					f[i][j][k] += f[i-1][x][mod(k-j,p)];
}
int dp(int n)
{
	if(!n) return 1;
	vector<int>nums;
	while(n) nums.push_back(n%10),n/=10;
	int last = 0;
	int res = 0;
	for(int i=nums.size()-1; i>=0; i--)
	{
		int x = nums[i];
		for(int j=0; j<x; j++)
			res += f[i+1][j][mod(-last,p)];
		last += x;
		if(!i && last%p==0) res ++;
	}
	return res ;
}
int main()
{
	int l,r;
	while(~scanf("%d%d%d",&l,&r,&p))
	{
		init();
		printf("%d\n",dp(r)-dp(l-1));
	}
	return 0;
}