这题规律其实挺明显的 打表找规律估计都可以 正规点就是DP
算出第N位所包含的good number的数量 如果给出的数是N+1位 就枚举各位上比原来小的数 加上下一位的dp值
一个i写成g了 纠结了半天。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define LL __int64
LL dp[][],a,b,pp;
void init()
{
int i,j,g;
for(i = ; i <= ; i++)
dp[][i] = ;
for(i = ; i <= ; i++)
for(j = ; j < ; j++)
for(g = ; g <= ; g++)
{
dp[i][(j+g)%] += dp[i-][j];
}
}
LL find(LL x)
{
int i,j,p[],g=;
while(x)
{
g++;
p[g] = x%;
pp+=p[g];
x/=;
}
int s=;
LL ss=;
for(i = g ; i >= ; i--)
{
for(j = ; j < p[i] ; j++)
{
int o = s+j;
if(i==)
{
if(o%==)
ss+=;
continue;
}
for(int k = ; k <= ; k++)
{
if((o+k)%==)
ss+=dp[i-][k];
}
}
s+=p[i];
}
return ss;
}
int main()
{
int t,i,kk=;
init();
scanf("%d",&t);
while(t--)
{
kk++;
scanf("%I64d%I64d",&a,&b);
LL s1 = find(a);pp=;
LL s2 = find(b);
if(pp%==)
s2++;
printf("Case #%d: ",kk);
printf("%I64d\n",s2-s1);
}
return ;
}