试填法裸题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[10][83][83][82],a[11],len;
int dfs(int pos,int sum,int res,int s,bool bk,int t)
{
if(sum>s)return 0;
else if(!bk)
return f[pos][s-sum][s][(s-res)%s];
else if(!pos)
{
if(sum==s&&!res)return 1;
return 0;
}
int ans=0;
for(int i=0;i<=a[pos];i++)//当前这一位填i
ans+=dfs(pos-1,sum+i,(res+i*t)%s,s,i==a[pos],t/10);
return ans;
}
int work(int x)
{
if(!x)return 0;
len=0;ll t=1;
while(x)a[++len]=x%10,x/=10,t*=10;
t/=10;
int ans=0;
for(int i=1;i<=81;i++)
ans+=dfs(len,0,0,i,1,t);
return ans;
}
int main()
{
for(int i=1;i<=81;i++)f[0][0][i][0]=1;
for(int i=1,t=1;i<=9;i++,t*=10)
for(int j=0;j<=i*9;j++)
for(int k=1;k<=81;k++)
for(int l=0;l<k;l++)
for(int p=0;p<=9&&p<=j;p++)
f[i][j][k][l]+=f[i-1][j-p][k][((l-p*t)%k+k)%k];
int l,r;
while(~scanf("%d%d",&l,&r))
qw(work(r)-work(l-1)),puts("");
return 0;
}
最后一次更新于2019-11-14
0 条评论