\(p^\alpha \mid \binom{n}{k}\) 即为 \(\binom{n}{k}\) 质因数分解后 \(p\) 的幂次 \(\geqslant \alpha\)。根据库默尔定理，\(\binom{n}{k}\) 中 \(p\) 的幂次即为 \(n-k\) 加上 \(k\) 在 \(p\) 进制下的进位次数。
那么问题就转化为了计算有多少对 \(p\) 进制非负数对 \((a,b)\)，满足 \(a+b \leqslant A\) 且 \(a+b\) 的进位次数 \(\geqslant \alpha\)。
考虑用数位 \(DP\) 来计算， 设 \(f_{i,j,0/1,0/1}\) 表示从最高位考虑到第 \(i\) 位，已有 \(j\) 次进位，是否有最高位的限制，是否有下一位向上进位的方案数，\(lim_i\) 为第 \(i\) 位最高位。
为方便转移，可以将转移过程中的一些量表示出来。
\(v_1=\frac{(p+1)p}{2}\)，其为当前位没有最高位限制，没有低位进位，不向高位进位的方案数，同时也是当前位没有最高位限制，没有低位进位，向高位进位的方案数。
\(v_2=\frac{(lim_i+1)lim_i}{2}\)，其为当前位有最高位限制但不等于 \(lim_i\)，没有低位进位，不向高位进位的方案数。
\(v_3=\frac{p(p-1)}{2}\)，其为当前位没有最高位限制，没有低位进位，向高位进位的方案数。
\(v_4=\frac{lim_i(2p-lim_i-1)}{2}\)，其为当前位有最高位限制但不等于 \(lim_i\)，没有低位进位，向高位进位的方案数。
\(v_5=\frac{lim_i(lim_i-1)}{2}\)，其为当前位有最高位限制但不等于 \(lim_i\)，有低位进位，不向高位进位的方案数。
\(v_6=\frac{lim_i(2p-lim_i+1)}{2}\)，其为当前位有最高位限制但不等于 \(lim_i\)，有低位进位，向高位进位的方案数。
这些方案数都可以先枚举一个值，然后考虑另一个值的合法范围，用等差数列求和即可。当前位置为 \(lim_i\) 且有最高位限制时，转移时的贡献即为合法范围大小，因为一个值确定后，另一个值也就确定了。
#include<bits/stdc++.h>
#define maxn 3510
#define P 1000000007
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c==‘-‘)flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,p,a,len,ans;
int t[maxn],f[maxn][maxn][2][2];
ll lim[maxn];
char s[maxn];
int main()
{
read(p),read(a),scanf("%s",s+1),len=strlen(s+1);
for(int i=1;i<=len;++i) t[i]=s[len-i+1]-‘0‘;
while(len)
{
ll v=0;
for(int i=len;i>=1;--i)
{
v=v*10+t[i],t[i]=v/p,v%=p;
if(!t[i]&&i==len) len--;
}
lim[++n]=v;
}
f[n+1][0][1][0]=1;
for(int i=n;i>=1;--i)
{
ll v1=(p+1)*p/2%P;
ll v2=(lim[i]+1)*lim[i]/2%P;
ll v3=p*(p-1)/2%P;
ll v4=lim[i]*(2*p-lim[i]-1)/2%P;
ll v5=lim[i]*(lim[i]-1)/2%P;
ll v6=lim[i]*(2*p-lim[i]+1)/2%P;
for(int j=0;j<=n-i;++j)
{
ll f1=f[i+1][j][0][0],f2=f[i+1][j][1][0],f3=f[i+1][j][0][1],f4=f[i+1][j][1][1];
f[i][j][0][0]=(f1*v1%P+f2*v2%P+f3*v3%P+f4*v4%P)%P;
f[i][j][1][0]=(f2*(lim[i]+1)%P+f4*(p-1-lim[i])%P)%P;
f[i][j+1][0][1]=(f1*v3%P+f2*v5%P+f3*v1%P+f4*v6%P)%P;
f[i][j+1][1][1]=(f2*lim[i]%P+f4*(p-lim[i])%P)%P;
}
}
for(int i=a;i<=n;++i) ans=(ans+f[1][i][0][0]+f[1][i][1][0])%P;
printf("%lld",ans);
return 0;
}
CF582D Number of Binominal Coefficients
原文：https://www.cnblogs.com/lhm-/p/13742150.html