10pts 求助
查看原帖
10pts 求助
360511
UperFicial楼主2022/5/24 15:52

枚举模数,然后记录数位和 sumsum 和数字 shushu

最后判断 shu=0&&sum=MOD

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<climits>
#include<set>
#include<iostream>
#define rint() read<int>()
#define rll() read<ll>()
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define f(a,b,c) dp.make_pair(a,make_pair(b,c))
using namespace std;
typedef long long ll;
inline int read()
{
	register int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){int t=x;x=y;y=t;return;}
const int MAXN(30);
const int MAXM(210);
int n;
ll l,r;
int res[MAXN],tot;
ll f[MAXN][MAXM][MAXM];
inline ll dfs(int p,bool limit,bool flag,int sum,int shu,int MOD)
{
	if(!p) return sum==MOD&&shu==0;
	if(!limit&&!flag&&f[p][sum][shu]!=-1) return f[p][sum][shu];
	int up=limit?res[p]:9;
	ll ans(0);
	rep(i,0,up)
		ans+=dfs(p-1,limit&&i==up,flag&&i==0,sum+i,(shu*10+i)%MOD,MOD);
	if(!limit&&!flag) f[p][sum][shu]=ans;
	return ans;
}
inline ll wei(ll x)
{
	tot=0;
	memset(f,-1,sizeof(f));
	while(x)
	{
		res[++tot]=x%10;
		x/=10;
	}
	int L=9*tot;
	ll ans(0);
	rep(MOD,1,L) ans+=dfs(tot,true,true,0,0,MOD);
	return ans; 
}
int main()
{
	scanf("%lld%lld",&l,&r);
	printf("%lld\n",wei(r)-wei(l-1));
	return 0;
}
2022/5/24 15:52
加载中...