-
Notifications
You must be signed in to change notification settings - Fork 0
/
LightOJ 1068
72 lines (66 loc) · 1.31 KB
/
LightOJ 1068
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dx[]= {0,0,1,-1,1,1,-1,-1};
ll dy[]= {1,-1,0,0,1,-1,1,-1};
ll tx[]= {2,2,1,1,-2,-2,-1,-1};
ll ty[]= {-1,1,-2,2,1,-1,-2,2};
ll t,a,b,k,ans;
vector<ll>num;
ll dp[12][84][2][83],num_size;
ll call(ll pos,ll x,ll f,ll y)
{
// cerr << f << " ";
if(pos==num_size)
{
if(x%k==0&&y==0)
return 1;
return 0;
}
if(dp[pos][x][f][y]!=-1)
return dp[pos][x][f][y];
ll lmt,res=0,tf,tx,ty;
if(f==0)
lmt=num[pos];
else
lmt=9;
for(ll i=0;i<=lmt;i++)
{
tf=f;
tx=x+i;
ty=(y*10+i)%k;
if(f==0&&i<lmt)
tf=1;
res+=call(pos+1,tx,tf,ty);
}
return dp[pos][x][f][y]=res;
}
ll solve(ll x)
{
num.clear();
while(x)
{
num.push_back(x%10);
x/=10;
}
num_size=num.size();
reverse(num.begin(),num.end());
memset(dp,-1,sizeof dp);
return call(0,0,0,0);
}
int main()
{
// freopen("f.txt","r",stdin);
// freopen("g.txt","w",stdout);
scanf("%lld",&t);
for(ll cas=1; cas<=t; cas++)
{
scanf("%lld%lld%lld",&a,&b,&k);
//cout<<b<<endl;
if(k >= 82)ans = 0;
else
ans=solve(b)-solve(a-1);
printf("Case %lld: %lld\n",cas,ans);
}
return 0;
}