题解
考虑 \(K=1\) 的做法
设 \(F_{i,j}\) 表示用 \(m^k\ (k\in [0,i])\) 凑出 \(j\) 的方案数
不难发现由于每次转移只会加入 \(m^{i+1}\) 那么有用的状态只有 \(j\equiv n\ (\mod m^i)\)
所以设 \(F_{i,j}\) 表示用 \(m^k\ (k\leq [0,i])\) 凑出 \(j\times m^i+(n \mod m^{i})\) 的方案数
\[ F_{i,j}=\sum\limits_{k=0}^j F_{i-1,(j-k)\times m+\lfloor \frac {n \mod m^{ i } }{m^{i-1}}\rfloor} \]可以观察并归纳证明 \(F_{i,j}\) 是一个关于 \(j\) 的 \(i\) 次多项式，所以只需要保留前 \(i\) 位的 $ DP $ 值，转移时通过拉格朗日插值求出用到的 \(DP\) 值来转移的即可，同样的只需要转移出前 \(i+1\) 项即可。
那么考虑求前缀和的问题，我们只需要在 $m^k (k\in[0,log_m n]) $ 这些数中额外加入一个 \(1\) 即可
如何扩展到 \(K>1\) ?
考虑 \(K\) 次卷积等效于将这个数划分 \(K\) 个部分求方案数即可，那么只需要将原先的 $m^k (k\in[0,log_m n]) $ 中每个数复制\(K\)遍，当做 \(K\) 个不同的数即可。
复杂度 \(O(K^2log_m^2 n)\times\) 巨大常数
#include#define LL long long#define mod 1000000007#define M 1410using namespace std;namespace IO{ const int BS=(1<<20)+5; int Top=0; char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1; char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;} void flush(){fwrite(OT,1,OS-OT,stdout),OS=OT;} void Putchar(char c){*OS++ =c;if(OS==fin)flush();} void write(int x){ if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-'); while(x) SS[++Top]=x%10,x/=10; while(Top) Putchar(SS[Top]+'0'),--Top; } LL read(){ LL nm=0,fh=1; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh; for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return nm*fh; }}using namespace IO;LL n,m,p[M],top;#define mul(a,b) ((LL)(a)*(LL)(b)%mod)#define add(a,b) (((a)+(b))>=mod?((a)+(b)-mod):((a)+(b)))#define mns(a,b) (((a)-(b))<0?((a)-(b)+mod):((a)-(b)))int K,C[M][M],fac[M],ifac[M],tot,A[M],B[M],pre[M],suf[M],F[M],G[M],t[M],pw[M];int qpow(int x,int sq){ int res=1; for(;sq;sq>>=1,x=mul(x,x)) if(sq&1) res=mul(res,x); return res;}void build(){for(int i=0;i<=tot;i++) t[i]=mul(G[i],mul(ifac[i],((i^tot)&1)?mns(0,ifac[tot-i]):ifac[tot-i]));}int calc(LL x){ x%=mod; if(x<=tot) return G[x]; int res=0; pre[0]=x,suf[tot+1]=1; for(int i=1;i<=tot+1;i++) pre[i]=mul(pre[i-1],mns(x,i)); for(int i=tot;i>=0;i--) suf[i]=mul(suf[i+1],mns(x,i)); for(int i=0;i<=tot;i++){ int t1=(i?pre[i-1]:1),t2=suf[i+1]; res=add(res,mul(t[i],mul(t1,t2))); } return res;}int main(){ n=read(),m=read(),K=read(),p[0]=fac[0]=ifac[0]=1; if(!n){puts("1");return 0;} for(int i=0;i