是一道卢卡斯定理题。。。
反正就是转成数位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));
}
}
Comments | NOTHING