NOIP模拟赛20191111 T3 密码【库默尔定理，DP计数】

题目描述：

求$\sum_{0\le s\le l\le n}[~p^k|C_l^s~]$0≤s≤l≤n∑​[ pk∣Cls​ ]
$1\le p,k\le10^9，n\le 10^{1000}$1≤p,k≤109，n≤101000

题目描述：

$C_n^m$Cnm​含$p$p的幂次$=\sum_{i=1}^{∞}[\dfrac{n}{p^i}]-[\dfrac{m}{p^i}]-[\dfrac{n-m}{p^i}]$=∑i=1∞​[pin​]−[pim​]−[pin−m​]，即$m$m与$n-m$n−m相加在$p$p进制下的进位次数，这是库默尔定理。

是否进位会影响当前位的决策，所以要记入状态，具体转移代码中有一点注释，供参考。
Code：

#include<bits/stdc++.h>
#define maxn 3505
using namespace std;
const int mod = 1e9+7;
int n,m,p,e,f[maxn][maxn][2][2],A[maxn],len,dig[maxn];
char S[1005];
void Divide(){
	int x=0;
	for(int i=len-1;i>=0;i--)
		A[i]=(x=x*10+A[i])/p,x%=p;
	while(len&&!A[len-1]) len--;
	dig[n++]=x;
}
inline int calc(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,&e);
	len=strlen(S);
	for(int i=0;i<len;i++) A[i]=S[len-i-1]-'0';
	while(len) Divide();
	if(e>=n) return puts("0"),0;
	reverse(dig,dig+n);
	f[0][0][0][1]=1;
	for(int i=0;i<n;i++) for(int j=0;j<=min(i,e);j++) for(int k=0;k<=1;k++){
		int cx=f[i][j][k][0],cy=f[i][j][k][1];
		for(int v=0;v<=1;v++){
			int nj=j==e?j:j+v;
			int &nx=f[i+1][nj][v][0],&ny=f[i+1][nj][v][1];
			if(!k){
				nx=(nx+1ll*cx*calc(p-v))%mod;//(x+y+v<p y=0->x=0~p-v-1)
				nx=(nx+1ll*cy*calc(dig[i]-v))%mod;//(x+y+v<dig[i] y=0->x=dig[i]-v-1~0)
				ny=(ny+1ll*cy*(dig[i]-v+1))%mod;//(x+y+v=dig[i] y=0->x=dig[i]-v)
			}
			else{
				nx=(nx+1ll*cx*calc(p-1+v))%mod;//(x+y+v>=p y=0->x=p-v y=p-v->y=0)
				nx=(nx+1ll*cy*(calc(p-1+v)-calc(p-dig[i]+v-1)+mod))%mod;//all-(x+y+v>=dig[i]+p y=p-1->x=dig[i]-v+1~p-1)
				ny=(ny+1ll*cy*(p-dig[i]+v-1))%mod;//(x+y+v=dig[i]+p y=p-1->x=dig[i]-v+1~p-1)
			}
		}
	}
	printf("%d\n",(f[n][e][0][0]+f[n][e][0][1])%mod);
}