题目链接

是一道卢卡斯定理题。。。

反正就是转成数位DP去做。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int i,j,k,x,y,t,T;
int f[71][2][2][2][2];
int numn[71],numm[71];
long long n,m;
//f1:first number < n?
//f2:second number < m?
//f3:satisfy numn<numm?
//f4:satiffy n>=m?
int DP(int p,int f1,int f2,int f3,int f4){
    if (p==1)return f3&f4;
    int &res=f[p][f1][f2][f3][f4];
    if (res!=-1)return res;
    int Ln,Lm;res=0;
    if (f1)Ln=k-1;else Ln=numn[p-1];
    if (f2)Lm=k-1;else Lm=numm[p-1];
    for (int a=0;a<=Ln;a++)
        for (int b=0;b<=Lm;b++)
            if (a<b){
                if (!f4)continue;
                int p1,p2;
                if (!f1&&a==Ln)p1=0;else p1=1;
                if (!f2&&b==Lm)p2=0;else p2=1;
                res=(res+DP(p-1,p1,p2,1,1))%mod;
            }
            else if (a==b){
                int p1,p2;
                if (!f1&&a==Ln)p1=0;else p1=1;
                if (!f2&&b==Lm)p2=0;else p2=1;
                res=(res+DP(p-1,p1,p2,f3,f4))%mod;
            }
            else if (a>b){
                int p1,p2;
                if (!f1&&a==Ln)p1=0;else p1=1;
                if (!f2&&b==Lm)p2=0;else p2=1;
                res=(res+DP(p-1,p1,p2,f3,1))%mod;
            }
    return res;
}
int main(){
    scanf("%d%d",&T,&k);
    while (T--){
        memset(f,-1,sizeof f);
        memset(numn,0,sizeof numn);
        memset(numm,0,sizeof numm);
        scanf("%lld%lld",&n,&m);
        while (n){
            numn[++numn[0]]=n%k;
            n/=k;
        }
        while (m){
            numm[++numm[0]]=m%k;
            m/=k;
        }
        numn[0]=max(numn[0],numm[0]);
        printf("%d\n",DP(numn[0]+1,0,0,0,0));
    }
}

优化了一下成了2ms..

蓝桥杯上有道差不多的题,只是k变成了1000000,这就不能枚举了,要大分类讨论。。。。。

只是有个点始终过不去。。。算了算了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int i,j,k,x,y,t,T;
int f[71][2][2][2][2];
int numn[71],numm[71];
long long n,m;
//f1:first number < n?
//f2:second number < m?
//f3:satisfy numn<numm?
//f4:satiffy n>=m?
int DP(int p,int f1,int f2,int f3,int f4){
    if (p==1)return f3&f4;
    int &res=f[p][f1][f2][f3][f4];
    if (res!=-1)return res;
    int Ln,Lm;res=0;
    if (f1)Ln=k-1;else Ln=numn[p-1];
    if (f2)Lm=k-1;else Lm=numm[p-1];
    if (f1&&f2){
        if (f4){
            res=(res+1ll*DP(p-1,1,1,1,1)*((1ll*k*(k-1)/2)%mod)%mod)%mod;
        }
        res=(res+1ll*DP(p-1,1,1,f3,f4)*k%mod)%mod;
        res=(res+1ll*DP(p-1,1,1,f3,1)*((1ll*k*(k-1)/2)%mod)%mod)%mod;
        return res;
    }
    if (!f1&&f2){
        if (f4){
            res=(res+1ll*DP(p-1,1,1,1,1)*((1ll*(k-1+k-numn[p-1])*(numn[p-1])/2)%mod)%mod)%mod;
            res=(res+1ll*DP(p-1,0,1,1,1)*(k-numn[p-1]-1)%mod)%mod;
        }
        res=(res+1ll*DP(p-1,1,1,f3,f4)*(numn[p-1])%mod)%mod;
        res=(res+DP(p-1,0,1,f3,f4))%mod;
        res=(res+1ll*DP(p-1,1,1,f3,1)*((1ll*(numn[p-1])*(numn[p-1]-1)/2)%mod)%mod)%mod;
        res=(res+1ll*DP(p-1,0,1,f3,1)*(numn[p-1])%mod)%mod;
        return res;
    }
    if (f1&&!f2){
        if (f4){
            res=(res+1ll*DP(p-1,1,1,1,1)*((1ll*(numm[p-1]-1)*(numm[p-1])/2)%mod)%mod)%mod;
            res=(res+1ll*DP(p-1,1,0,1,1)*numm[p-1]%mod)%mod;
        }
        res=(res+1ll*DP(p-1,1,1,f3,f4)*(numm[p-1])%mod)%mod;
        res=(res+DP(p-1,1,0,f3,f4))%mod;
        res=(res+1ll*DP(p-1,1,1,f3,1)*((1ll*(k-1+k-numm[p-1])*numm[p-1]/2)%mod)%mod)%mod;
        res=(res+1ll*DP(p-1,1,0,f3,1)*(k-1-numm[p-1])%mod)%mod;
        return res;
    }
    if (!f1&&!f2){
        if (f4){//1<2
            if (numn[p-1]>=numm[p-1]){
                res=(res+1ll*DP(p-1,1,1,1,1)*((1ll*(numm[p-1]-1)*(numm[p-1])/2)%mod)%mod)%mod;
                res=(res+1ll*DP(p-1,1,0,1,1)*numm[p-1]%mod)%mod;
            }
            else{
                res=(res+1ll*DP(p-1,1,1,1,1)*((1ll*(numm[p-1]-1+numm[p-1]-numn[p-1])*numn[p-1]/2)%mod)%mod)%mod;
                res=(res+1ll*DP(p-1,1,0,1,1)*numn[p-1]%mod)%mod;
                res=(res+1ll*DP(p-1,0,1,1,1)*(numm[p-1]-1-numn[p-1])%mod)%mod;
                res=(res+DP(p-1,0,0,1,1))%mod;
            }
        }
        //-----
        res=(res+1ll*DP(p-1,1,1,f3,f4)*min(numn[p-1],numm[p-1])%mod)%mod;
        if (numn[p-1]>numm[p-1])res=(res+DP(p-1,1,0,f3,f4))%mod;
        if (numn[p-1]==numm[p-1])res=(res+DP(p-1,0,0,f3,f4))%mod;
        if (numn[p-1]<numm[p-1])res=(res+DP(p-1,0,1,f3,f4))%mod;
        //------
        if (numn[p-1]<=numm[p-1]){
            res=(res+1ll*DP(p-1,1,1,f3,1)*((1ll*(numn[p-1])*(numn[p-1]-1)/2)%mod)%mod)%mod;
            res=(res+1ll*DP(p-1,0,1,f3,1)*(numn[p-1])%mod)%mod;
        }
        else{
            res=(res+1ll*DP(p-1,1,1,f3,1)*((1ll*(numn[p-1]-1+numn[p-1]-numm[p-1])*numm[p-1]/2)%mod)%mod)%mod;
            res=(res+1ll*DP(p-1,0,1,f3,1)*numm[p-1]%mod)%mod;
            res=(res+1ll*DP(p-1,1,0,f3,1)*(numn[p-1]-1-numm[p-1])%mod)%mod;
            res=(res+DP(p-1,0,0,f3,1))%mod;
        }
        return res;
    }
}
int main(){
    scanf("%d%d",&T,&k);
    while (T--){
        memset(f,-1,sizeof f);
        memset(numn,0,sizeof numn);
        memset(numm,0,sizeof numm);
        scanf("%lld%lld",&n,&m);m=min(m,n);
        while (n){
            numn[++numn[0]]=n%k;
            n/=k;
        }
        while (m){
            numm[++numm[0]]=m%k;
            m/=k;
        }
        printf("%d\n",DP(numn[0]+1,0,0,0,0));
    }
}


告别纷扰,去寻找生活的宝藏。