CF582D Number of Binominal Coefficients 题解

CF582D Number of Binominal Coefficients 题解

纪念一下自己第一道独立 A 掉的黑题 / CF3300。

题目大意

给定质数 \(p\) 和整数 \(\alpha,A\)，求满足 \(0 \le k \le n \le A\) 且 \(p^{\alpha}|\binom nk\) 的数对 \((n,k)\) 的个数。

Solve

首先，我们引入 Kummer定理，即：

\(p\) 在组合数 \(n\choose m\) 中的幂次，恰好为 \(n\) 与 \(m\) 做 \(p\) 进制减法的借位次数。

所以我们只需统计 \(n\) 与 \(k\) 做 \(p\) 进制减法时借位次数大于等于 \(\alpha\) 的 \((n,k)\) 的个数即可。

Step 1

将 \(A\) 在 \(p\) 进制下数位分离，记其第 \(i\) 位为 \(a_i\)。

我们考虑如下常规数位 dp：设 \(f(i,j,0/1,0/1)\) 表示：前 \(i+1\) 位，借位次数为 \(j\)，\(n\) 是否卡满了 \(A\) 的上界，\(k\) 是否卡满了 \(n\) 的上界，这种状态的 \((n,k)\) 的个数。

但是，我们这一位是否借位，是和下一位（更小的那一位）是否借位有关的，如果下一位借位了，那么我们这一位相等时也可以借位，所以考虑多加一维，变为：\(f(i,j,0/1,0/1,0/1)\) 表示：前 \(i+1\) 位，借位次数为 \(j\)，\(n\) 是否卡满了 \(A\) 的上界，\(k\) 是否卡满了 \(n\) 的上界，钦定这一位借位 / 不借位，这种状态的 \((n,k)\) 的个数。那么我们有如下朴素的转移：

枚举第 \(i\) 位的 \(n\) 填 \(i'\)，\(k\) 填 \(j'\)，有：

\[f(i-1,j,f1\vee[i'<a_i],f2\vee[j'<i'],f3)\longleftarrow f(i,j,f1,f2,0),\quad i'-f3-j'\geq0\\ f(i-1,j+1,f1\vee[i'<a_i],f2\vee[j'<i'],f3)\longleftarrow f(i,j,f1,f2,1),\quad i'-f3-j'<0 \]

\(f1,f2,f3\) 为枚举状态，常规的 \(f1,f2\) 对 \(i',j'\) 的限制就不再讨论了，要注意的是 \(f3\)，即是否钦定下一位借位，的限制。

时间复杂度约为 \(O(p^2\log_pA)\)，但本题 \(p\leq 10^9\)，考虑优化。

Step 2

上面的转移中，\(j'\) 的作用不是很大，所以我们只需枚举始状态 \(f1,f2,f3\)，再枚举这一位上是否借位（\(y\)），\(j'<i'\) 是否成立（\(g2\)），下一位是否借位（\(g3\)），受算一下即可求出相应状态下合法的 \(j\) 的取值范围 \([l,r]\)，那么我们有：

\[f(i-1,j+y,f1\vee[i'<a_i],f2\vee g2,g3)\longleftarrow (r-l+1)f(i,j,f1,f2,f3). \]

\(l\) 和 \(r\) 是好确定的，简单写一下吧，为后面化简做准备。

\[l=\max \begin{cases} 0\\ i'+1-g3&f3=1\vee y=1\\ i'& g2=0\\ \end{cases}\\ r=\min \begin{cases} p-1\\ i'-g3&f2=0\vee f3=0\vee y=0\\ i'-1&g2=1 \end{cases} \]

时间复杂度约为 \(O(p\log_pA)\)。考虑更深一步讨论，尽量省去 \(i'\) 和一些参数的枚举。

Step 3

一步一步来，对参数分别讨论。上面的式子中，我们需保证 \(l\leq r\)，所以据此讨论。

容易发现，当 \(f3=1\) 时，\(f2\) 也必须等于 \(1\)，因为若 \(f3=1,f2=0\)，那么 \(l\geq i'+1-g3,r\leq i'-g3\Longrightarrow l>r\)。

同样的，我们有，\(y=f3\)，也是对 \(l\) 和 \(r\) 的第二行式子讨论可得。

并且，当 \(f3=1\) 时，\(g2\) 只能是 \(0\)，因为若 \(g2=1\)，那么 \(r=i'-1<l=i'+1-g3\)。

由此，我们有了更优美的转移式：

\[f(i-1,j+1,f1\vee[i'<a_i],1,g3)\longleftarrow (r-l+1)\cdot f(i,j,f1,1,1).\\ f(i-1,j,f1\vee[i'<a_i],g2,g3)\longleftarrow (r-l+1)\cdot f(i,j,f1,0,0).\\ f(i-1,j,f1\vee[i'<a_i],1,g3)\longleftarrow (r-l+1)\cdot f(i,j,f1,1,0).\\ [l,r]= \begin{cases} [i'+1-g3,p-1]&f3=1\wedge g2=0\\ [i',i'-g3]&f3=0\wedge g2=0\\ [0,i'-1]&f3=0\wedge g2=1 \end{cases} \]

考虑把 \(l,r\) 的讨论转化为 \(r-l+1\)，即系数的讨论，简单化简得：

\[\begin{align} &f(i-1,j+1,f1\vee[i'<a_i],1,g3)\longleftarrow (p-1-i'+g3)\cdot f(i,j,f1,1,1)\\ \iff &\begin{cases} f(i-1,j+1,f1\vee[i'<a_i],1,0)\longleftarrow (p-1-i')\cdot f(i,j,f1,1,1)\\ f(i-1,j+1,f1\vee[i'<a_i],1,1)\longleftarrow (p-i')\cdot f(i,j,f1,1,1)\\ \end{cases}\\ \\ &f(i-1,j,f1\vee[i'<a_i],0,g3)\longleftarrow (1-g3)\cdot f(i,j,f1,0,0)\\ \iff &f(i-1,j,f1\vee[i'<a_i],0,0)\longleftarrow f(i,j,f1,0,0)\\ \\ &f(i-1,j,f1\vee[i'<a_i],1,g3)\longleftarrow i'\cdot f(i,j,f1,0,0)\\ \iff &\begin{cases} f(i-1,j,f1\vee[i'<a_i],1,0)\longleftarrow i'\cdot f(i,j,f1,0,0)\\ f(i-1,j,f1\vee[i'<a_i],1,1)\longleftarrow i'\cdot f(i,j,f1,0,0)\\ \end{cases}\\ \\ &f(i-1,j,f1\vee[i'<a_i],1,g3)\longleftarrow (i'+1-g3)\cdot f(i,j,f1,1,0)\\ \iff &\begin{cases} f(i-1,j,f1\vee[i'<a_i],1,0)\longleftarrow (i'+1)\cdot f(i,j,f1,1,0)\\ f(i-1,j,f1\vee[i'<a_i],1,1)\longleftarrow i'\cdot f(i,j,f1,1,0)\\ \end{cases} \end{align} \]

时间复杂度仍约为 \(O(p\log_pA)\)，只是优化了一些参数的枚举，枚举 \(i'\) 的瓶颈仍未拿下。

Step 4

化简之后，可以发现第四维的枚举用处不大，所以我们令 \(f'(i,j,f1,f2)=f(i,j,f1,0,f2)+f(i,j,f1,1,f2)\)，有：

\[\begin{align} &\begin{cases} f'(i-1,j+1,f1\vee[i'<a_i],0)\longleftarrow (p-1-i')\cdot f'(i,j,f1,1)\\ f'(i-1,j+1,f1\vee[i'<a_i],1)\longleftarrow (p-i')\cdot f'(i,j,f1,1)\\ \end{cases}\\ &\begin{cases} f'(i-1,j,f1\vee[i'<a_i],0)\longleftarrow (i'+1)\cdot f'(i,j,f1,0)\\ f'(i-1,j,f1\vee[i'<a_i],1)\longleftarrow i'\cdot f'(i,j,f1,0)\\ \end{cases} \end{align} \]

然后，对 \(i'\) 的讨论就很明了了，分为 \(i<a_i\) 和 \(i\geq a_i\) 两种情况即可，几个转移式的系数都是等差数列求和，很好算。

时间复杂度成功优化到约 \(O(log_pA)\)。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{char c=getchar();int now=0;short f=1;while(c<'0'||c>'9')	{if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')	now=(now<<1)+(now<<3)+(c^48),c=getchar();return now*f;
}
const int N=3350,MOD=1e9+7,M=1010;
using ll=long long;
int p,c,f[2][N/*借位次数*/][2/*i=A*/][2/*这一位是否需要借位*/],n,a[N],ans;
struct zzn//高精度封装，只需实现 除以低精 和 对低精取模，好写的
{int num[M],len;zzn(){len=0;memset(num,0,sizeof num);}inline void read(){char s[M];scanf("%s",s+1);len=strlen(s+1);for(int i=1;i<=len;i=-~i)	num[i]=s[len-i+1]-'0';}inline void print(){for(int i=len;i;i=~-i)printf("%d",num[i]);}zzn operator/(const int b)const{zzn res;res.len=len;ll r=0;for(int i=len;i;i=~-i)r=10ll*r+num[i],res.num[i]=r/b,r%=b;while(!res.num[res.len]&&res.len)	res.len=~-res.len;return res;}int operator%(const int b)const{int res=0;for(int i=len;i;i=~-i)	res=(10ll*res+num[i])%b;return res;}
}A;
signed main()
{p=read();c=read();A.read();while(A.len)	a[n=-~n]=A%p,A=A/p;f[n&1][0][0][0]=1;for(int now=n;now;now=~-now)for(int x=0;x<=n-now;x=-~x)for(int f1=0;f1<2;f1=-~f1){int t0=f[now&1][x][f1][0],t1=f[now&1][x][f1][1];f[now&1][x][f1][0]=f[now&1][x][f1][1]=0;int i0=(f1?p-1:a[now]);//i枚举上界//对于i<a[now](f[now&1^1][x][1][1]+=1ll*(a[now]-1)*a[now]/2%MOD*t0%MOD)%=MOD,(f[now&1^1][x][1][0]+=1ll*(a[now]+1)*a[now]/2ll%MOD*t0%MOD)%=MOD;(f[now&1^1][x+1][1][1]+=1ll*(p*2-a[now]+1)*a[now]/2%MOD*t1%MOD)%=MOD,(f[now&1^1][x+1][1][0]+=1ll*(p*2-a[now]-1)*a[now]/2%MOD*t1%MOD)%=MOD;//对于i>=a[now](f[now&1^1][x][f1][1]+=1ll*(a[now]+i0)*(i0-a[now]+1)/2%MOD*t0%MOD)%=MOD,(f[now&1^1][x][f1][0]+=1ll*(a[now]+i0+2)*(i0-a[now]+1)/2%MOD*t0%MOD)%=MOD;(f[now&1^1][x+1][f1][1]+=1ll*(p*2-a[now]-i0)*(i0-a[now]+1)/2%MOD*t1%MOD)%=MOD,(f[now&1^1][x+1][f1][0]+=1ll*(p*2-a[now]-i0-2)*(i0-a[now]+1)/2%MOD*t1%MOD)%=MOD;//下为暴力枚举 i 的转移
//				for(int i=0;i<=i0;i=-~i)
//				{
//					(f[now&1^1][x+f2][f1|(i<a[now])][1]+=1ll*i*t0%MOD)%=MOD,
//					(f[now&1^1][x+f2][f1|(i<a[now])][0]+=1ll*(i+1)*t0%MOD)%=MOD;
//					(f[now&1^1][x+f2][f1|(i<a[now])][1]+=1ll*(p-i)*t1%MOD)%=MOD,
//					(f[now&1^1][x+f2][f1|(i<a[now])][0]+=1ll*(p-i-1)*t1%MOD)%=MOD;
//				}}for(int i=c;i<=n;i=-~i)for(int j=0;j<2;j=-~j)(ans+=f[0][i][j][0])%=MOD;return printf("%d",ans),0;
}

再附上不同 Step 的代码。

• Step 1：\(O(p^2\log_pA)\)。
• Step 2：\(O(p\log_pA)\)。
• Step 3：\(O(p\log_pA)\)。