【XSY4186】Binomial(结论,数位DP)

题面

Binomial

题解

设 ord ⁡ ( n ) \operatorname{ord}(n) ord(n) 表示 n n n 分解质因数后 p p p 的幂次,那么我们就是对于每一个 k k k 要求有多少 0 ≤ m ≤ n 0\leq m\leq n 0≤m≤n 使得 ord ⁡ ( C n m ) = k \operatorname{ord}\left(C_n^m\right)= k ord(Cnm​)=k。

首先有一个很显然的式子: ord ⁡ ( n ! ) = ∑ k = 1 ∞ ⌊ n p k ⌋ \operatorname{ord}(n!)=\sum\limits_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k}\right\rfloor ord(n!)=k=1∑∞​⌊pkn​⌋,于是:
ord ⁡ ( C n m ) = ord ⁡ ( n ! m ! ( n − m ) ! ) = ∑ k = 1 ∞ ( ⌊ n p k ⌋ − ⌊ m p k ⌋ − ⌊ n − m p k ⌋ ) \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) ord(Cnm​)=ord(m!(n−m)!n!​)=k=1∑∞​(⌊pkn​⌋−⌊pkm​⌋−⌊pkn−m​⌋)
考虑把 n , m , n − m n,m,n-m n,m,n−m 都用 p p p 进制表示:

【XSY4186】Binomial(结论,数位DP)

此时 ⌊ n p k ⌋ \left\lfloor\dfrac{n}{p^k}\right\rfloor ⌊pkn​⌋ 就相当于 n n n 右移 k k k 位,于是我们把第 k k k 位这一条分界线画出来,那么 n n n 在分界线左边的部分就相当于 ⌊ n p k ⌋ \left\lfloor\dfrac{n}{p^k}\right\rfloor ⌊pkn​⌋, n n n 在分界线右边的部分就相当于 n   m o d   p k n\bmod p^k nmodpk。 ⌊ m p k ⌋ , ⌊ n − m p k ⌋ \left\lfloor\dfrac{m}{p^k}\right\rfloor,\left\lfloor\dfrac{n-m}{p^k}\right\rfloor ⌊pkm​⌋,⌊pkn−m​⌋ 同理。

如果你把这看作一个减法竖式的话(即 n − m n-m n−m,当然看成加法竖式 m + ( n − m ) m+(n-m) m+(n−m) 也是可以的),就会发现:若减法过程中分界线右边没有向分界线左边借位( n   m o d   p k ≥ m   m o d   p k n \bmod p^k\geq m\bmod p^k nmodpk≥mmodpk),那么就有 ⌊ n p k ⌋ − ⌊ m p k ⌋ = ⌊ n − m 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 ⌊pkn​⌋−⌊pkm​⌋=⌊pkn−m​⌋;若减法过程中分界线右边有向分界线左边借位( n   m o d   p k < m   m o d   p k n \bmod p^k< m\bmod p^k nmodpk<mmodpk),那么就有 ( ⌊ n p k ⌋ − 1 ) − ⌊ m p k ⌋ = ⌊ n − m 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 (⌊pkn​⌋−1)−⌊pkm​⌋=⌊pkn−m​⌋。

于是就可以写成:
ord ⁡ ( C n m ) = ∑ k = 1 ∞ [ m   m o d   p k > n   m o d   p k ] \operatorname{ord}(C_n^m)=\sum_{k=1}^{\infty}\left[m\bmod p^k>n\bmod p^k\right] ord(Cnm​)=k=1∑∞​[mmodpk>nmodpk]
于是就可以数位 DP 了:设 f ( k , ord ⁡ , 0 / 1 ) f(k,\operatorname{ord},0/1) f(k,ord,0/1) 表示考虑完 m m m 的末 k k k 位, ∑ k ′ = 1 k [ m   m o d   p k ′ > n   m o d   p k ′ ] \sum_{k'=1}^{k}\left[m\bmod p^{k'}>n\bmod p^{k'}\right] ∑k′=1k​[mmodpk′>nmodpk′] 为 ord ⁡ \operatorname{ord} ord,其中是否满足 [ m   m o d   p k > n   m o d   p k ] \left[m\bmod p^{k}>n\bmod p^{k}\right] [mmodpk>nmodpk] 的 m m m 的个数。直接转移即可。

这里和平常不同,是从低位往高位 DP 的,那如果最后 m > n m>n m>n 怎么办呢?你发现我们刚好记录了 0 / 1 0/1 0/1 表示是否满足 [ m   m o d   p k > n   m o d   p k ] \left[m\bmod p^{k}>n\bmod p^{k}\right] [mmodpk>nmodpk],那么最后 f ( ∣ n ∣ , ∗ , 0 ) f(|n|,*,0) 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;
}
上一篇:java swing写五子棋小游戏(完整代码)


下一篇:剑指 Offer II 014. 字符串中的变位词