蒟蒻求助qaq
查看原帖
蒟蒻求助qaq
552688
clx201022楼主2024/3/15 21:58
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int N=1000;
string l,r;
int num[N+1];
struct memory
{
    ll data;
    bool used;
}f[N+1][11][11][2];
ll dfs(int pos,int d,int ld,bool limit,bool hui_wen){
	if(pos==0) return hui_wen;
	if(!limit&&f[pos][d][ld][hui_wen].used)return f[pos][d][ld][hui_wen].data;
	int up=(!limit?9:num[pos-1]);
    ll wer=0;
	for(int i=0;i<=up;i++)
    {
		wer+=dfs(pos-1,i,d
        ,limit&&i==up
        ,hui_wen||i==d||i==ld);
        wer%=mod;
    }
	if(!limit)f[pos][d][ld][hui_wen].data=wer,f[pos][d][ld][hui_wen].used=1;
	return wer;
}
ll shu_wei_dp(string n,short pianyi)//偏移量
{
    unsigned n_len=n.size();
    ll res=0;
	for(unsigned i=0;i<n_len;i++)
        num[i]=n[n_len-i-1]-'0';
	num[0]+=pianyi;
	if(n_len==1&&num[0]<=0)//为 0
        return 0;
	for(unsigned i=0;i+1<n_len&&num[i]<0;i++)
	{
        num[i]+=10;
        num[i+1]--;
    }
	while(n_len>=2&&num[n_len-1]==0)
        n_len--;
	for(int i=0;i<=N;i++)
        for(int j=0;j<11;j++)
            for(int o=0;o<11;o++)
                for(int z=0;z<2;z++)
                    f[i][j][o][z].used=0;
	for(unsigned i=1;i<n_len-1;i++)
		for(int j=1;j<=9;j++)//1~9
			res=(res+dfs(i-1,j,10,0,0))%mod;
	for(int j=1;j<=num[n_len-1];j++)
		res=(res+dfs(n_len,j,10,j==num[n_len-1],0))%mod;
	return res;
}

int main(){
	cin>>l>>r;
	cout<<((shu_wei_dp(r,0)-shu_wei_dp(l,-1))%mod+mod)%mod<<endl;
	return 0;
}
2024/3/15 21:58
加载中...