WA 63pts 求调
查看原帖
WA 63pts 求调
685993
Akagi_shigeru楼主2023/2/12 10:15

rt,本人几乎直接把P3413的代码搬了过来,但是WA成了63pts

#include<bits/stdc++.h>
using namespace std;
namespace my_IO{
    #define ll long long
    #define ull unsigned long long
    #define ld long double
    template<class T>
    void read(T &num){
        T x=0,f=1;
        char c=getchar();
        while(!isdigit(c)){
            if(c=='-') f=-1;
            c=getchar();
        }
        while(isdigit(c)){
            x=(x<<3)+(x<<1)+c-48;
            c=getchar();
        }
        num=x*f;
    }
    template<class T>
    void write(T x){
        static char buf[40];
        int len=-1;
        if(x<0) putchar('-'),x=-x;
        do{
            buf[++len]=x%10+48;
            x/=10;
        }while(x);
        while(len>=0) putchar(buf[len--]);
    }
}
using namespace my_IO;
const ll mod=1e9+7;
ll l,r,num[20],f[20][10][10][2];
ll get(ll x){
    ll res=0;
    while(x){
        res++;
        x/=10;
    }
    return res;
}
ll dfs(ll pos,ll lim,ll led,ll pre1,ll pre2,ll flag){
    if(!pos) return flag;
    if(!lim&&!led&&pre1!=-1&&pre2!=-1&&f[pos][pre1][pre2][flag]!=-1) return f[pos][pre1][pre2][flag];
    ll ans=0,up=lim?num[pos]:9;
    for(ll i=0;i<=up;i++) ans=(ans+dfs(pos-1,lim&&i==up,led&&!i,(led&&!i)?-1:i,led?-1:pre1,flag||(!led&&i==pre1)||(!led&&i==pre2)))%mod;
    if(!lim&&!led&&pre1!=-1&&pre2!=-1) return f[pos][pre1][pre2][flag]=ans;
    return ans;
}
ll work(ll x){
    if(x==-1) return 0;
    ll len=get(x);
    for(ll i=1;i<=len;i++){
        num[i]=x%10;
        x/=10;
    }
    memset(f,-1,sizeof(f));
    return dfs(len,1,1,-1,-1,0);
}
void solve(){
    read(l),read(r);
    ll a=work(l-1),b=work(r);
    write(((r-(l-1))%mod-(b-a+mod)%mod+mod)%mod);
}
int main(){
    int t=1;
    while(t--) solve();
}
2023/2/12 10:15
加载中...