0分求助
查看原帖
0分求助
360511
UperFicial楼主2022/5/26 11:51

高精度将 ll 减一,然后答案为 rlsumr-l-sumsumsum(l,r](l,r] 的非蒙数。

调了两天了快吐了,球球帮忙康一下/kel

#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))
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(1010);
const int MOD(1e9+7);
int dp[MAXN][12][12];
char l[MAXN],r[MAXN];
int l1,l2;
int tot,a[MAXN];
inline int add(int x,int y){return x+y>MOD?x+y-MOD:x+y;}
inline int dfs(int p,bool limit,bool flag,int pre1,int pre2)
{
	if(!p) return 1;
	if(!limit&&!flag&&dp[p][pre1+1][pre2+1]!=-1) return dp[p][pre1+1][pre2+1];
	int up=limit?a[p]:9;
	int ans(0);
	rep(i,0,up) if(i!=pre1&&i!=pre2) ans=add(ans,dfs(p-1,limit&&i==up,flag&&i==0,flag&&i==0?-1:i,pre1));
	if(!limit&&!flag) dp[p][pre1+1][pre2+1]=ans;
	return ans;
}
inline int solve(char*s,int len)
{
	tot=len;
	rep(i,1,tot) a[i]=s[i]-'0';
	reverse(a+1,a+1+tot);
	memset(dp,-1,sizeof(dp));
	return dfs(tot,true,true,-1,-1);
}
inline int getnum(char*s,int len)
{
	int res(0);
	rep(i,1,len) res=(1ll*res*10+1ll*(s[i]-'0'))%MOD;
	return res;
}
inline int jianyi()
{
	int n=strlen(l+1);
	int b[MAXN];
	rep(i,1,n) b[i]=l[i]-'0';
	int p=n;
	b[p]--;
	while(b[p]<0&&p!=1)
	{
		b[p]+=10;
		b[p-1]--;
		--p;
	}
	if(b[p]==0&&p<n) ++p;
	int j(0);
	rep(i,p,n) l[++j]=b[i]+'0';
	return j;
}
int main()
{
	scanf("%s%s",l+1,r+1);
	l1=jianyi(),l2=strlen(r+1);    
	printf("%d\n",((getnum(r,l2)-getnum(l,l1)-(solve(r,l2)-solve(l,l1)))%MOD+MOD)%MOD);
	return 0;
}
2022/5/26 11:51
加载中...