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 的代码。
标签：Binominal,f1,f2,f3,CF582D,题解,借位,now,MOD From： https://www.cnblogs.com/sorato/p/18441395