给定n,m和k,求有多少对(i , j)满
足0 ≤ i ≤ n, 0 ≤ j ≤ min(i ,m)且C(︀i，j)︀是k的倍数.
n,m ≤ 1018, k ≤ 100,且k是质数.
把i和j都看成k进制数，事实上这个问题就是问有多少
对j ≤ i满足j有一位比i大.
转化成数位DP
对每一位进行转移
bool判断是否当前位n<=a[i],m<=b[i]
By：大奕哥
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+;
ll inv=500000004ll;
int T;
ll f[][][],a[],b[],k; ll calc(ll x,ll y)
{
if(x<||y<)return ;
if(x<y)return 1ll*((x+)%mod*(x+)%mod)%mod*inv%mod;
return (1ll*(y+)%mod*((y+)%mod)%mod*inv%mod+1ll*(x-y)%mod*((y+)%mod)%mod)%mod;
}
int main()
{
scanf("%d%lld",&T,&k);
while(T--)
{
int n=,m=;long long x,y;
scanf("%lld",&x);ll t=x;
while(t)
{
a[++n]=t%k;t/=k;
}
scanf("%lld",&y);y=min(y,x);t=y;
while(t)
{
b[++m]=t%k;t/=k;
}
long long ans=calc(x,y);
f[][][]=;
for(int i=;i<=n;++i)
{
f[i][][]=(calc(a[i],b[i])*f[i-][][]%mod+calc(a[i],b[i]-)*f[i-][][]%mod+calc(a[i]-,b[i])*f[i-][][]%mod+calc(a[i]-,b[i]-)*f[i-][][]%mod)%mod;
f[i][][]=(calc(k-,b[i])*(f[i-][][]+f[i-][][])%mod+calc(k-,b[i]-)*(f[i-][][]+f[i-][][])%mod-f[i][][]+mod)%mod;
f[i][][]=(calc(a[i],k-)*(f[i-][][]+f[i-][][])%mod+calc(a[i]-,k-)*(f[i-][][]+f[i-][][])%mod-f[i][][]+mod)%mod;
f[i][][]=(((calc(k-,k-)*(f[i-][][]+f[i-][][]+f[i-][][]+f[i-][][])%mod-f[i][][]+mod)%mod-f[i][][]+mod)%mod-f[i][][]+mod)%mod;
}
printf("%lld\n",(ans-f[n][][]+mod)%mod);
while(n)a[n--]=;
while(m)b[m--]=;
}
}