【JZOJ5330】【NOIP提高组模拟】密码（库默尔定理、数位DP）

Description

Solution

这题和[51Nod 1569二项式系数的个数]是用一道题。
就是要求Cmn|pk
根据库默尔定理，Cmn中p的次幂数就是n+m（加法）在p进制下的进位次数。
那么题意就变成了选小于等于n的两个数，在p进制下的进位次数为k。
知道这个之后我们就可以数位DP。
我们设f[i][j][k][l]表示做到第i为，进位次数为j，下一位是否要进位，是否顶着上界。
因为要考虑进位，所以下一位如果要进位的话那么这一位还要+1。
那么80分的话这个转移的时候就直接p^2枚举。
然后我们可以发现这p^2个转移其实就是一些等差数列，这里需要细细讨论。
只要把80分的思路想清晰，100分的不会很难想。

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=2507,mo=1e9+7;
ll f[maxn][maxn][2][2],ans;
ll i,j,k,l,t,n,m,p,u,v;
ll a[maxn],b[maxn],c[maxn],o,yi,er,pp,pp1;
char s[maxn];
int main(){
    freopen("password.in","r",stdin);
    freopen("password.out","w",stdout);
    scanf("%s%lld%lld",s+1,&p,&k);n=strlen(s+1);
    fo(i,1,n)b[n-i+1]=s[i]-'0';b[0]=n;
    while(b[0]){
        o=0;c[0]=0;
        fod(i,b[0],1){
            b[i]+=o*10;
            o=b[i]%p;b[i]/=p;
        }
        while(b[0]&&!b[b[0]])b[0]--;
        a[++a[0]]=o;
    }
    n=a[0];fo(i,1,n)c[i]=a[n-i+1];fo(i,1,n)a[i]=c[i];
    if(k>n){printf("0\n");return 0;}
    f[0][0][0][1]=1;yi=p*(p-1)/2%mo;er=p*(p+1)/2%mo;
    fo(i,1,n){
        pp=(a[i]*p%mo+(a[i]+p+1)*(p-a[i])/2%mo-er)%mo;
        pp1=(a[i]*p%mo+(a[i]+p)*(p-a[i]-1)/2%mo+a[i]-yi)%mo;
        fo(j,0,n){
            if(j){
                f[i][j][0][0]=(f[i][j][0][0]+f[i-1][j-1][1][0]*yi%mo+f[i-1][j-1][1][1]*pp%mo)%mo;
                f[i][j][0][1]=(f[i][j][0][1]+f[i-1][j-1][1][1]*(p-1-a[i])%mo)%mo;           
            }
            if(j){
                f[i][j][1][0]=(f[i][j][1][0]+f[i-1][j-1][1][0]*er%mo+f[i-1][j-1][1][1]*pp1%mo)%mo;
                f[i][j][1][1]=(f[i][j][1][1]+f[i-1][j-1][1][1]*(p-a[i])%mo)%mo;
            }
            f[i][j][0][0]=(f[i][j][0][0]+f[i-1][j][0][0]*er%mo+f[i-1][j][0][1]*(((1+a[i])*a[i]/2)%mo)%mo)%mo;
            f[i][j][0][1]=(f[i][j][0][1]+f[i-1][j][0][1]*(a[i]+1)%mo)%mo;
            f[i][j][1][0]=(f[i][j][1][0]+f[i-1][j][0][0]*yi%mo+f[i-1][j][0][1]*((a[i]*(a[i]-1)/2)%mo)%mo)%mo;
            f[i][j][1][1]=(f[i][j][1][1]+f[i-1][j][0][1]*a[i]%mo)%mo;
        }
    }
    fo(i,k,n)ans=(ans+f[n][i][0][1]+f[n][i][0][0])%mo;
    printf("%lld\n",ans);
}