给定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：大奕哥
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 ll inv=500000004ll; 6 int T; 7 ll f[70][2][2],a[70],b[70],k; 8 9 ll calc(ll x,ll y) 10 { 11 if(x<0||y<0)return 0; 12 if(x<y)return 1ll*((x+2)%mod*(x+1)%mod)%mod*inv%mod; 13 return (1ll*(y+2)%mod*((y+1)%mod)%mod*inv%mod+1ll*(x-y)%mod*((y+1)%mod)%mod)%mod; 14 } 15 int main() 16 { 17 scanf("%d%lld",&T,&k); 18 while(T--) 19 { 20 int n=0,m=0;long long x,y; 21 scanf("%lld",&x);ll t=x; 22 while(t) 23 { 24 a[++n]=t%k;t/=k; 25 } 26 scanf("%lld",&y);y=min(y,x);t=y; 27 while(t) 28 { 29 b[++m]=t%k;t/=k; 30 } 31 long long ans=calc(x,y); 32 f[0][1][1]=1; 33 for(int i=1;i<=n;++i) 34 { 35 f[i][1][1]=(calc(a[i],b[i])*f[i-1][1][1]%mod+calc(a[i],b[i]-1)*f[i-1][1][0]%mod+calc(a[i]-1,b[i])*f[i-1][0][1]%mod+calc(a[i]-1,b[i]-1)*f[i-1][0][0]%mod)%mod; 36 f[i][0][1]=(calc(k-1,b[i])*(f[i-1][1][1]+f[i-1][0][1])%mod+calc(k-1,b[i]-1)*(f[i-1][1][0]+f[i-1][0][0])%mod-f[i][1][1]+mod)%mod; 37 f[i][1][0]=(calc(a[i],k-1)*(f[i-1][1][1]+f[i-1][1][0])%mod+calc(a[i]-1,k-1)*(f[i-1][0][1]+f[i-1][0][0])%mod-f[i][1][1]+mod)%mod; 38 f[i][0][0]=(((calc(k-1,k-1)*(f[i-1][1][1]+f[i-1][1][0]+f[i-1][0][1]+f[i-1][0][0])%mod-f[i][1][1]+mod)%mod-f[i][0][1]+mod)%mod-f[i][1][0]+mod)%mod; 39 } 40 printf("%lld ",(ans-f[n][1][1]+mod)%mod); 41 while(n)a[n--]=0; 42 while(m)b[m--]=0; 43 } 44 }