- 给定(n,m)和一个质数(k)，求有多少(0le ile n,0le jlemin{i,m})，满足(C_i^j)是(k)的倍数。
- 数据组数(le100,n,mle10^{18},kle100)
卢卡斯定理
显然有一个基本结论：
[k|C_i^jLeftrightarrow C_i^jequiv0(mod k)
]
由于(k)是质数，我们可以直接套用卢卡斯定理：
[C_i^jequiv C_{i div k}^{j div k} imes C_{i mod k}^{j mod k}(mod k)
]
也就是说，如果我们把(i,j)转化为(k)进制数，只要有一位(i)比(j)小就为(0)。
所以就可以整一个数位(DP)了。
数位(DP)
我们设(f_{x,p,fn,fm})表示从高往低(DP)到第(x)位，(p=0/1/2)分别表示(i,j)一直相等/出现过(i>j)但没出现过(i<j)/出现过(i>j)然后出现过(i<j)（注意，题目里要求(jle i)，所以必须先出现(i>j)），(fn=0/1)表示(i)是否小于(n)，(fm=0/1)表示(j)是否小于(m)。
转移就是分别枚举它们这一位填什么数即可。
代码：(O(Tlog_kn))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define L 60
#define X 1000000007
using namespace std;
long long N,M;int k,Mx,n[L+5],m[L+5];
int f[L+5][3][2][2];I int DP(CI x,CI p,CI fn,CI fm)//数位DP
{
if(!x) return p==2;if(~f[x][p][fn][fm]) return f[x][p][fn][fm];//记忆化
RI i,j,t=0,sn=fn?k-1:n[x],sm=fm?k-1:m[x];for(i=0;i<=sn;++i)
for(j=0;j<=(p?sm:min(sm,i));++j) t=(t+DP(x-1,p?(p==1?1+(i<j):2):(i>j),fn||i^n[x],fm||j^m[x]))%X;//枚举i,j这位填什么数
return f[x][p][fn][fm]=t;
}
int main()
{
RI Tt,i;scanf("%d%d",&Tt,&k);W(Tt--) {memset(f,-1,sizeof(f)),Mx=0,
scanf("%lld%lld",&N,&M);W(N||M) n[++Mx]=N%k,m[Mx]=M%k,N/=k,M/=k;printf("%d
",DP(Mx,0,0,0));}return 0;//分解为k进制数
}