题解 CF582D 【Number of Binominal Coefficients】
smarthehe
·
·
题解
库默尔定理
定理：\binom{n+m}{m} 中质数 p 的幂次为 n 与 m 的 p 进制表示相加的进位次数。
有了这个定理以后，题意就可以转化成求有多少对 n,m 相加小于 A，且在 p 进制下相加的进位次数 \geq \alpha。设计一个数位 dp。
$dp_{i,j,0,0} \rightarrow dp_{i+1,j,0/1,0}$：等于上界 $x$（0），实际值 $x$，系数为 $x+1$；小于上界 $x$（1），实际值 $0$ 到 $x-1$，系数为 $\frac{x(x+1)}{2}
dp_{i,j,0,0} \rightarrow dp_{i+1,j+1,0/1,1}$：等于上界 $x$（0），实际值 $x-1$，系数为 $x$；小于上界 $x$（1），实际值 $0$ 到 $x-2$，系数为 $\frac{(x-1)x}{2}
dp_{i,j,0,1} \rightarrow dp_{i+1,j,0/1,0}$：等于上界 $x$（0），实际值 $p+x$，系数为 $p-1-x$；小于上界 $x$（1），实际值 $p$ 到 $p+x-1$，系数为 $\frac{x(2p-1-x)}{2}
dp_{i,j,0,1} \rightarrow dp_{i+1,j+1,0/1,1}$：等于上界 $x$（0），实际值 $p-1+x$，系数为 $p+1-x$；小于上界 $x$（1），实际值 $p-1$ 到 $p-1+x-1$，系数为 $\frac{x(2p+1-x)}{2}
$dp_{i,j,1,0} \rightarrow dp_{i+1,j+1,1,1}$：任取，和 $< p-1$。系数为 $\frac{(p-1)p}{2}$。
$dp_{i,j,1,1} \rightarrow dp_{i+1,j,1,0}$：任取，和 $\geq p$。系数为 $\frac{(p-1)p}{2}$。
$dp_{i,j,1,1} \rightarrow dp_{i+1,j+1,1,1}$：任取，和 $\geq p-1$。系数为 $\frac{p(p+1)}{2}$。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=3505,MOD=1e9+7;
char s[N];
long long lim[N];
int lc=1,dp[N][N][2][2];
int main()
{
int p,a,n,i,j;
scanf("%d%d%s",&p,&a,s+1);n=strlen(s+1);
for(i=1;i<=n;i++)
{
for(j=1;j<=lc;j++) lim[j]=10ll*lim[j];
lim[1]+=s[i]-'0';
for(j=1;j<=lc;j++)
{
lim[j+1]+=lim[j]/p;
lim[j]%=p;
if(lim[lc+1]) lc++;
}
}
for(i=1;i<=lc/2;i++) swap(lim[i],lim[lc-i+1]);
dp[0][0][0][0]=1;
for(i=0;i<lc;i++)
{
int x=lim[i+1];
for(j=0;j<=i;j++)
{
dp[i+1][j][0][0]=(dp[i+1][j][0][0]+1ll*(x+1)*dp[i][j][0][0])%MOD;
dp[i+1][j][1][0]=(dp[i+1][j][1][0]+1ll*(1ll*x*(x+1)/2%MOD)*dp[i][j][0][0])%MOD;
dp[i+1][j+1][0][1]=(dp[i+1][j+1][0][1]+1ll*x*dp[i][j][0][0])%MOD;
dp[i+1][j+1][1][1]=(dp[i+1][j+1][1][1]+1ll*(1ll*(x-1)*x/2%MOD)*dp[i][j][0][0])%MOD;
dp[i+1][j][0][0]=(dp[i+1][j][0][0]+1ll*(p-1-x)*dp[i][j][0][1])%MOD;
dp[i+1][j][1][0]=(dp[i+1][j][1][0]+1ll*(1ll*x*(p*2-1-x)/2%MOD)*dp[i][j][0][1])%MOD;
dp[i+1][j+1][0][1]=(dp[i+1][j+1][0][1]+1ll*(p-x)*dp[i][j][0][1])%MOD;
dp[i+1][j+1][1][1]=(dp[i+1][j+1][1][1]+1ll*(1ll*x*(p*2+1-x)/2%MOD)*dp[i][j][0][1])%MOD;
dp[i+1][j][1][0]=(dp[i+1][j][1][0]+1ll*(1ll*p*(p+1)/2%MOD)*dp[i][j][1][0])%MOD;
dp[i+1][j+1][1][1]=(dp[i+1][j+1][1][1]+1ll*(1ll*(p-1)*p/2%MOD)*dp[i][j][1][0])%MOD;
dp[i+1][j][1][0]=(dp[i+1][j][1][0]+1ll*(1ll*(p-1)*p/2%MOD)*dp[i][j][1][1])%MOD;
dp[i+1][j+1][1][1]=(dp[i+1][j+1][1][1]+1ll*(1ll*p*(p+1)/2%MOD)*dp[i][j][1][1])%MOD;
}
}
int ans=0;
for(i=a;i<=lc;i++) ans=(0ll+ans+dp[lc][i][0][0]+dp[lc][i][1][0])%MOD;
printf("%d",ans);
return 0;
}
```