本题的数据范围究极大。

按NOIP提高组在2016有过一样的题.不过数据规模就这道题的1~4结点。用组合数的递推公式加上二维前缀和维护即可。

洛谷的弱化数据版AC代码如下：

#include<bits/stdc++.h>
#define MAXN 2005
using namespace std;
typedef long long ll;
int t;
ll c[MAXN][MAXN],ans[MAXN][MAXN],n,m,k;
ll Init(){
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<=2000;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=((c[i-1][j-1]+c[i-1][j]))%k;
            ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
            if(!c[i][j])
                ans[i][j]++;
        }
        ans[i][i+1]=ans[i][i];
    }
} 
int main(){
    scanf("%d%lld",&t,&k);
    Init();
    while(t--){
        scanf("%lld%lld",&n,&m);
        if(m>n)
            printf("%lld\n",ans[n][n]);
        else
            printf("%lld\n",ans[n][m]);
    }
    return 0;
}

 

不过显然对于这题毒瘤一般的数据范围想拿到满分是不可能的。

所以这题其实是和清华2016集训里的一道题一模一样的。包括数据范围。

对于这题我们需要用到卢卡斯定理。将n和m都转化为p进制数。

根据卢卡斯定理，如果模k为0，那么n的p进制中的存在一数位小于m中对应数位上的值即可。

但计算至少存在一个这种终归很麻烦，所以还是要用到正难则反的思想。

我们求出n和m的组合数总数，再减去n中每一数位都大于m的数量。即可得到答案。

思路和代码来源于：https://blog.csdn.net/xuxiaobo1234/article/details/108096786

求n中每一数位都大于m的数量我们可以用到数位DP。

先定义4种状态：

dp[i][0] :表示前i位n和m都没限制的数量

dp[i][1] :n的前i位都有限制，m前i位都无限制

dp[i][2] :m的前i位都有限制，n的前i位都无限制

dp[i][3] :n，m的前i位都有限制

再定义3个函数：

calc(x,y)：x取值[0, x], y取值[0,y]，x >=y的数量

calc1(x,y)：x固定，y取值为[0,y] ，x >= y的数量

calc2x,y)：y固定，x取值为[0,x] ，x >= y的数量

最后状态转移方程：

dp[i][0] = dp[i+1][0] * calc(P-1, P-1) + dp[i+1][1] * calc(a[i]-1, P-1) + dp[i+1][2] * calc(P-1, b[i]-1) + dp[i+1][3] * calc(a[i]-1, b[i]-1);

前i位n和m都没限制的数量为前i+1位都没限制的数量*这一数位上n大于m的选择数量。（其中calc（P-1,P-1）表示由于无限制。故该数位n可以取0~P-1，m可以取0~P-1,在这种情况下n数位大于m的情况数）

其他同理

dp[i][1] = dp[i+1][1] * calc1(a[i], P-1) + dp[i+1][3] * calc1(a[i], b[i]-1);

dp[i][2] = dp[i+1][2] * calc2(P-1, b[i]) + dp[i+1][3] * calc2(a[i]-1, b[i]);

dp[i][3] = dp[i+1][3] & (a[i] >= b[i]);（dp[i][3]是记录前i位都有限制的情况。故要么为1要么为0.（因为这相当于直接判断n和m是否满足条件））

一些小细节：

在求x>=y的数量时。由于值过大。我们需要再模之后再除2.但直接除是会有问题的。故我们应该乘2相对于模数的乘法逆元再模模数。这样就能得到答案。

AC代码如下（注释写的应该也挺清楚）：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
const LL Mod = 1e9+7;
const LL inv_2 = 5e8+4;//inv_2是2对于Mod的逆元。即inv_2=（Mod+1）/2 。
LL dp[65][4];
/*
用卢卡斯定理后转化为n，m的k进制数中，n中至少有一位大于m则模k为0.
考虑对立事件，求出n中所有位都大于m的对数，在用总方案减去它 
*/
LL calc(LL x, LL y){//x取值[0, x], y取值[0,y] x >=y的数量 
    if(x<0||y<0) 
        return 0;
    if(x<y){
        x%=Mod; 
        y%=Mod;
        return (x+2)*(x+1)%Mod*inv_2%Mod;//如果x小于y，则共有（x+1）*（x+2）/2种
    }
      x%=Mod;y%=Mod;
      return ((y+2)*(y+1)%Mod*inv_2%Mod+(x-y)*(y+1)%Mod)%Mod;//y大于x。则(y+1)*(y+2)/2+(x-y)(y+1) 
}
LL calc1(LL x,LL y) { // x不变，y取值为[0,y] x >= y的数量 
      return min(x,y)+1;
}
LL calc2(LL x,LL y) { // y不变 x取值为[0,x] x >= y的数量 
      if(x<y) return 0;
      return x-y+1;
}
LL a[100], b[100], P;
int main(){
    int t;
    scanf("%d%lld",&t,&P);
    while(t--){
        LL n, m, ans;
        scanf("%lld%lld",&n,&m);
        if(m>n)//如果给的m大于n了。那么大于n的部分也是不可能取到的。故将m重置为n 
            m=n;
        ans=calc(n,m);//对于给定的n,m有多少个组合数 
        int lenn=0,lenm=0;
        while(n)//记录n在p进制下每一数位的值 
            a[lenn++]=n%P,n/=P;
        while(m)//记录m在p进制下每一数位的值 
            b[lenm++]=m%P,m/=P;
        memset(dp,0,sizeof(dp));
        dp[lenn][3]=1;//最高位n和m都到了上界 
        for(int i=lenn-1;~i;i--){//因为没限制，且是p进制数。故每一位的取值是0~p-1. 
            dp[i][0]=dp[i+1][0]*calc(P-1,P-1)+dp[i+1][1]*calc(a[i]-1,P-1)//因为n有限制故…… 
                      +dp[i+1][2]*calc(P-1,b[i]-1)+dp[i+1][3]*calc(a[i]-1,b[i]-1);
            dp[i][1]=dp[i+1][1]*calc1(a[i], P-1)+dp[i+1][3]*calc1(a[i],b[i]-1);
            dp[i][2]=dp[i+1][2]*calc2(P-1, b[i])+dp[i+1][3]*calc2(a[i]-1,b[i]);
            dp[i][3]=dp[i+1][3]&(a[i] >= b[i]);//dp[i][3] :n，m的前i位都到达了上界
            dp[i][0]%=Mod;//dp[i][0] :第i位无限制 
            dp[i][1]%=Mod;//dp[i][1] :n的前i位为上界，m未达上界 
            dp[i][2] %= Mod;//dp[i][2] :m的前i位位上界，n未达上界 
            a[i]=b[i]=0;//清空。以后也用不到了。 
        }
        ans-=dp[0][0]+dp[0][1]+dp[0][2]+dp[0][3];//减去一个都不大于的情况就是至少有一个的情况 
        ans=((ans%Mod)+Mod)%Mod;//ans最小整模数 
        printf("%lld\n",ans);
    }
}