定义运算符$!$如下：
$$n!k=\left\{ \begin{array} {cc} n!(k-1)\times(n-1)!k, & (n>0,\;k>0) \\ 1, & (n=0) \\ n, & (k=0) \\ \end{array} \right. $$
给定$n,\,k$，求$n!k$的不同约数个数，对$1e9+9$取模。
$0<\;n\le\;1000,\;0<\;k\le\;100$
虽然$n!k$的值增长非常迅速，并且不能对它取模，很难分解求答案，但其实不用考虑那么多。
把$n$和$k$的不同取值得到的$n!k$看成$0\sim n \times 0\sim k$的矩阵，那么容易发现所有的数值都以第$0$列为因子。
那么只需要做出$1e3$以内的质数，递推累加指数就可以了。经测得到这样的质数有$168$个。
设$f_{i,j,p}$表示$n!k$的第$p$个质数的指数。可以把第一维用滚动数组将内存优化到$2$倍。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define IL inline using namespace std; typedef long long LL; const int N=1000; const int K=100; const int M=168; const int mod=1e9+9; IL LL add(LL x,LL y){ return (x+y)%mod; } IL LL mul(LL x,LL y){ return x*y%mod; } int n,k; bool npm[N+3]; LL prm[M+3]; int m; IL void flt(){ memset(npm,0,sizeof npm); m=0; for(int i=2;i<=N;i++) if(!npm[i]){ prm[++m]=i; for(int j=1;j<=m&&i*prm[j]<=N;j++) npm[i*prm[j]]=true; } else for(int j=1;j<=m&&i*prm[j]<=N;j++){ npm[i*prm[j]]=true; if(i%prm[j]==0) break; } } LL f[2][K+3][M+3]; IL void dsv(LL i){ LL ii=i; memset(f[i&1][0],0,sizeof f[i&1][0]); for(int j=1;j<=m&&prm[j]<=i;j++) while(i%prm[j]==0){ i/=prm[j]; f[ii&1][0][j]+=1; } } int main(){ scanf("%d%d",&n,&k); flt(); memset(f,0,sizeof f); for(LL i=1;i<=n;i++){ dsv(i); for(int j=1;j<=k;j++) for(int p=1;p<=m;p++) f[i&1][j][p]=add(f[(i-1)&1][j][p],f[i&1][j-1][p]); } LL ans=1; for(int i=1;i<=m;i++) ans=mul(ans,f[n&1][k][i]+1); printf("%lld",ans); return 0; }
观察答案的来源，溯流而上求解。
原文：https://www.cnblogs.com/Hansue/p/11370238.html
