P6669 组合数问题

https://www.luogu.com.cn/problem/P6669
数位dp+lucas定理

给顶 (n,m,k)，求 对于 (0le ile n,0le jle min(i,m))，有多少对 ((i,j)) 满足 ( binom{i}{j}) 是 (k) 的倍数

其实要求的就是 ( binom{i}{j}mod k=0) 的个数
由于 (k) 是小质数，所以可以根据 lucas 定理，转换为要求有多少 (i=(a_1 a_2cdots a_p)_kle n,j=(b_1 b_2cdots b_p)_kle min(i,m))，使得 (dbinom{a_1}{b_1}cdot dbinom{a_2}{b_2}cdots dbinom{a_p}{b_p}mod k=0)
其中，((a_1 a_2cdots a_p)_k,(b_1 b_2cdots b_p)_k) 是 (i,j) 的 (k) 进制展开形式，(p) 取它们之间较大的位数
那么上述式子 (mod k) 为 (0)，当且仅当存在一个 (u)，使得 (a_u<b_u)

然后就是做一个 (k) 进制下的数位dp，(f(pos,ok,ij,in,jm)) 表示当前是第 (pos) 位，满足条件的 (u) 是否已经出现过，后三位分别表示 (i,j)、(i,n)、(j,m) 之间顶不顶上界
就可以记忆化搜索了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN puts("")
inline long long read(){
	register long long x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}
#define mod 1000000007
int k;
long long n,m;
long long f[68][2][2][2][2];
int nn[68],mm[68];
long long work(int pos,int ok,int ij,int in,int jm){
	if(!pos) return ok;
	long long &ret=f[pos][ok][ij][in][jm];
	if(~ret) return ret;
	ret=0;
	int limi=in?nn[pos]:(k-1),limj=jm?mm[pos]:(k-1);
	for(reg int i=0;i<=limi;i++)for(reg int j=0;j<=limj&&(j<=i||!ij);j++){
		ret=(ret+work(pos-1,ok|(i<j),ij&(i==j),in&(i==limi),jm&(j==limj)))%mod;
	}
	return ret;
}
int main(){
	int T=read();k=read();
	while(T--){
		n=read();m=read();
		std::memset(nn,0,sizeof nn);std::memset(mm,0,sizeof mm);
		nn[0]=mm[0]=0;
		while(n) nn[++nn[0]]=n%k,n/=k;
		while(m) mm[++mm[0]]=m%k,m/=k;
		std::memset(f,-1,sizeof f);
		printf("%lld
",work(std::max(nn[0],mm[0]),0,1,1,1));
	}
	return 0;
}