CSP模拟赛20191111 密码（数位DP）

$n<=1e1000,p<=1e9,k<=1e9$n<=1e1000,p<=1e9,k<=1e9
请注意$p \ is \ prime$p is prime

对于一个$\binom ls = \frac {l!}{s!(l-s)!}$(sl​)=s!(l−s)!l!​
其含有的$p$p的最大次数$k$k满足$p^k | \binom ls$pk∣(sl​)为：
$k = \sum_{i} \frac l{p^i} - \frac s{p^i} - \frac {l-s}{p^i}$k=i∑​pil​−pis​−pil−s​
我们在$p$p进制下看待这个问题。
$k$k就是在$p$p进制下$s$s与$l-s$l−s做加法时进了多少位。
所以转进制后直接数位$DP$DP即可。
一开始没想到数位$DP$DP可以直接维护进位什么的。。。。。。。
标程写得好。

$\rm AC \ Code$AC Code

#include<bits/stdc++.h>
#define maxn 4005
#define mod 1000000007
#define LL long long
using namespace std;

char S[maxn];
int p,K,la,lb,f[2][maxn][2][2];
LL a[maxn],b[maxn];

int cal(int x){ return 1ll * x * (x+1) / 2 % mod; }

int main(){
	
	freopen("password.in","r",stdin);
	freopen("password.out","w",stdout);
	
	scanf("%s%d%d",S,&p,&K),la=strlen(S);
	for(int i=0;i<la;i++) a[i]=S[la-i-1]-'0';
	for(;la;){
		for(int i=la-1;i>=0;i--){
			if(i) a[i-1] += a[i] % p * 10;
			else b[lb++] = a[i] % p;
			a[i] /= p;
		}
		for(;la && !a[la-1];la--);
	}
	if(K > lb){
		puts("0");
		return 0;
	}
	int nw = 1 , pe = 0;
	f[nw][0][0][1] = 1;
	for(int i=lb-1;i>=0;i--){
		swap(nw,pe);
		memset(f[nw],0,sizeof f[nw]);
		for(int j=0;j<lb-i;j++)
			for(int k=0;k<2;k++){
				int pf = f[pe][j][k][1] , pb = f[pe][j][k][0];
				for(int e=0;e<2;e++){
					int nj = (j == K ? j : j+e);
					int &nf = f[nw][nj][e][1] , &nb = f[nw][nj][e][0];
					if(!k){
						nb = (nb + (LL)pb*cal(p-e) + (LL)pf*cal(b[i]-e) ) % mod;
						nf = (nf + (LL)pf*(b[i]-e+1)) % mod;
					}				
					else{
						nb = (nb + (LL)pb*cal(p+e-1) + (LL)pf*(cal(p+e-1)-cal(p+e-1-b[i]))) % mod;
						nf = (nf + (LL)pf*(p+e-1-b[i])) % mod;
					}
				}
			}
	}
	printf("%d\n",((f[nw][K][0][0]+f[nw][K][0][1])%mod+mod)%mod);
}