题面
题解
设 \(\operatorname{ord}(n)\) 表示 \(n\) 分解质因数后 \(p\) 的幂次，那么我们就是对于每一个 \(k\) 要求有多少 \(0\leq m\leq n\) 使得 \(\operatorname{ord}\left(C_n^m\right)= k\)。
首先有一个很显然的式子：\(\operatorname{ord}(n!)=\sum\limits_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k}\right\rfloor\)，于是：
\[\operatorname{ord}(C_n^m)=\operatorname{ord}\left(\dfrac{n!}{m!(n-m)!}\right)=\sum_{k=1}^{\infty}\left(\left\lfloor\dfrac{n}{p^k}\right\rfloor-\left\lfloor\dfrac{m}{p^k}\right\rfloor-\left\lfloor\dfrac{n-m}{p^k}\right\rfloor\right) \]考虑把 \(n,m,n-m\) 都用 \(p\) 进制表示：
此时 \(\left\lfloor\dfrac{n}{p^k}\right\rfloor\) 就相当于 \(n\) 右移 \(k\) 位，于是我们把第 \(k\) 位这一条分界线画出来，那么 \(n\) 在分界线左边的部分就相当于 \(\left\lfloor\dfrac{n}{p^k}\right\rfloor\)，\(n\) 在分界线右边的部分就相当于 \(n\bmod p^k\)。\(\left\lfloor\dfrac{m}{p^k}\right\rfloor,\left\lfloor\dfrac{n-m}{p^k}\right\rfloor\) 同理。
如果你把这看作一个减法竖式的话（即 \(n-m\)，当然看成加法竖式 \(m+(n-m)\) 也是可以的），就会发现：若减法过程中分界线右边没有向分界线左边借位（\(n \bmod p^k\geq m\bmod p^k\)），那么就有 \(\left\lfloor\dfrac{n}{p^k}\right\rfloor-\left\lfloor\dfrac{m}{p^k}\right\rfloor=\left\lfloor\dfrac{n-m}{p^k}\right\rfloor\)；若减法过程中分界线右边有向分界线左边借位（\(n \bmod p^k< m\bmod p^k\)），那么就有 \(\left(\left\lfloor\dfrac{n}{p^k}\right\rfloor-1\right)-\left\lfloor\dfrac{m}{p^k}\right\rfloor=\left\lfloor\dfrac{n-m}{p^k}\right\rfloor\)。
于是就可以写成：
\[\operatorname{ord}(C_n^m)=\sum_{k=1}^{\infty}\left[m\bmod p^k>n\bmod p^k\right] \]于是就可以数位 DP 了：设 \(f(k,\operatorname{ord},0/1)\) 表示考虑完 \(m\) 的末 \(k\) 位，\(\sum_{k'=1}^{k}\left[m\bmod p^{k'}>n\bmod p^{k'}\right]\) 为 \(\operatorname{ord}\)，其中是否满足 \(\left[m\bmod p^{k}>n\bmod p^{k}\right]\) 的 \(m\) 的个数。直接转移即可。
这里和平常不同，是从低位往高位 DP 的，那如果最后 \(m>n\) 怎么办呢？你发现我们刚好记录了 \(0/1\) 表示是否满足 \(\left[m\bmod p^{k}>n\bmod p^{k}\right]\)，那么最后 \(f(|n|,*,0)\) 就是我们要的答案了。
代码如下：
#include<bits/stdc++.h>
#define N 4010
#define ll long long
using namespace std;
namespace modular
{
const int mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
}using namespace modular;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct BigInt
{
int len,a[N];
}n,nn;
int p,K;
char s[N];
void turnp()
{
while(n.len)
{
ll r=0;
for(int i=n.len;i>=1;i--)
{
r=10ll*r+n.a[i];
n.a[i]=r/p;
r%=p;
}
while(n.len&&!n.a[n.len]) n.len--;
nn.a[++nn.len]=r;
}
n=nn;
}
int f[N][N][2];
int ans[N];
int main()
{
// freopen("binom2.in","r",stdin);
// freopen("binom2.out","w",stdout);
p=read(),K=read();
scanf("%s",s+1);
n.len=strlen(s+1);
for(int i=1;i<=n.len;i++) n.a[i]=s[n.len-i+1]-'0';
turnp();
f[0][0][0]=1;
for(int k=1;k<=n.len;k++)
{
for(int j=0;j<=n.len;j++)
{
f[k][j][0]=add(mul(n.a[k]+1,f[k-1][j][0]),mul(n.a[k],f[k-1][j][1]));
f[k][j+1][1]=add(mul(p-n.a[k]-1,f[k-1][j][0]),mul(p-n.a[k],f[k-1][j][1]));
}
}
for(int i=n.len;i>=0;i--)
ans[i]=add(f[n.len][i][0],ans[i+1]);
for(int i=0;i<=K;i++)
printf("%d ",ans[i]);
return 0;
}