UOJ275 [清华集训2016] 组合数问题 【Lucas定理】【数位DP】

题目分析：

我记得很久以前有人跟我说NOIP2016的题目出了加强版在清华集训中，但这似乎是一道无关的题目？

由于$k$为素数，那么$lucas$定理就可以搬上台面了。

注意到$\binom{i}{j} \equiv 0 {\mod k}$当且仅当将$i$和$j$用$k$进制表示的时候，有一位上的$i<j$。

位数上的计算用数位DP就没错了。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int mod = ;

 int t,k;

 long long n,m;

 int bn[],n1,n2,bm[],nw[];

 int f[][][]; //0 0~k-1 1 0~self

 int sum[][],pw[],dd[],oo[],fw[],yw[];

 void init(){

     if(n < m) m = n;

     memset(bn,,sizeof(bn)); memset(bm,,sizeof(bm)); n1 = ,n2 = ;

     long long p1 = n,p2 = m;

     while(p1){bn[++n1] = p1 % k; p1 /= k;}

     while(p2){bm[++n2] = p2 % k; p2 /= k;}

     dd[] = ;oo[] = ;

     for(int i=;i<=n1;i++) dd[i] = (dd[i-] + 1ll*bm[i]*pw[i-]%mod)%mod;

     for(int i=;i<=n1;i++) oo[i] = (oo[i-] + 1ll*bn[i]*pw[i-]%mod)%mod;

 }

 pair<int,int> dfs3(int now){

     if(now == ){return make_pair(,);}

     int ans1 = ,ans2 = ;

     pair<int,int> pt = dfs3(now-);

     int cutp = min(bn[now]+,bm[now]);

     for(int i=;i<bn[now];i++){

     int cuep = min(i+,bm[now]);

     ans1 += (1ll*cuep*sum[now-][])%mod; ans1 %= mod;

     ans1 += (1ll*(bm[now]-cuep)*pw[now-])%mod*pw[now-]%mod;ans1%=mod;

     if(bm[now] > i){ans1 += (1ll*pw[now-]*dd[now-])%mod; ans1 %= mod;}

     else{ans1 += nw[now-];ans1 %= mod;}

     ans2 += (1ll*(i+)*sum[now-][])%mod; ans2 %= mod;

     ans2 += (1ll*(k-i-)*pw[now-]%mod*pw[now-])%mod; ans2 %= mod;

     }

     ans1 += (1ll*cutp*pt.second)%mod; ans1 %= mod;

     ans1 += (1ll*(bm[now]-cutp)*oo[now-]%mod*pw[now-])%mod;ans1 %= mod;

     if(bm[now] > bn[now]){ans1 += (1ll*oo[now-]*dd[now-])%mod;ans1%=mod;}

     else{ans1 += pt.first;ans1 %= mod;}

     ans2 += (1ll*(bn[now]+)*pt.second)%mod; ans2 %= mod;

     ans2 += (1ll*(k-bn[now]-)*oo[now-])%mod*pw[now-]%mod;ans2 %= mod;

     return make_pair(ans1,ans2);

 }

 void work(){

     memset(f,,sizeof(f));memset(sum,,sizeof(sum));memset(nw,,sizeof(nw));

     for(int i=;i<=n1;i++){

     for(int j=;j<k;j++){

         f[i][j][] = (1ll*j*sum[i-][]+sum[i-][]+f[i][j][])%mod;

         f[i][j][] += (1ll*(j+)*sum[i-][])%mod; f[i][j][] %= mod;

         f[i][j][] += (1ll*(k-j-)*((1ll*pw[i-]*pw[i-])%mod))%mod;

         f[i][j][] %= mod;

         sum[i][] += f[i][j][]; sum[i][] %= mod;

         sum[i][] += f[i][j][]; sum[i][] %= mod;

     }

     }

     int ans = ;

     for(int now=;now<=n1;now++){

     int ans1 = ,ans2 = ;

     for(int i=;i<bm[now];i++){

         ans1 = (ans1 + 1ll*sum[now-][]*(i+))%mod;

         ans1 +=(1ll*pw[now-]*pw[now-])%mod*(bm[now]--i)%mod;ans1%=mod;

         ans1 += (1ll*pw[now-]*dd[now-])%mod; ans1 %= mod;

         ans2 += (1ll*(i+)*sum[now-][])%mod; ans2 %= mod;

         ans2 += ((1ll*(k-i-)*pw[now-])%mod*pw[now-])%mod; ans2 %= mod;

     }

     ans2 = (ans2+1ll*yw[now-]*(bm[now]+))%mod;

     ans2+=((1ll*pw[now-]*(k-bm[now]-))%mod*dd[now-])%mod;ans2%=mod;

     ans1 = (1ll*yw[now-]*bm[now]+fw[now-]+ans1)%mod;

     fw[now] = ans1; yw[now] = ans2;

     }

     for(int now=;now<=n1;now++){

     for(int i=;i<bm[now];i++){

         nw[now] += (1ll*pw[now-]*i%mod*pw[now-])%mod; nw[now] %= mod;

         nw[now] = (nw[now]+1ll*(k-i)*sum[now-][])%mod;

     }

     nw[now] += 1ll*bm[now]*pw[now-]%mod*dd[now-]%mod; nw[now] %= mod;

     nw[now] = (nw[now]+1ll*(k-bm[now])*nw[now-])%mod;

     }

     ans += fw[n1];ans-=(m%mod*((m+)%mod)/2ll)%mod; if(ans < ) ans += mod;

     pair<int,int> ans2 = dfs3(n1);

     ans = ans + (ans2.first-fw[n1]); ans %= mod; ans += mod; ans %= mod;

     printf("%d\n",ans);

 }

 int main(){

     scanf("%d%d",&t,&k);

     pw[] = ; for(int i=;i<=;i++) pw[i] = (1ll*pw[i-]*k)%mod;

     while(t--){

     scanf("%lld%lld",&n,&m);

     init(); work();

     }

     return ;

 }