题目
分析
- 这道题显然我们需要先找规律
- 这里一个矩阵,代表
- 1 1 1 1 1
- 2 2 2 2 2
- 6 12 24 48
- 24 288....
- 所以当前数等于左边乘上面
- 左边一列是阶乘
- 然后我们要求的是约数个数
- 就要分解质因数
- 我们举个例子,24=4*6; 4=2^2,6=2*3 24=2^3*3
- 所以我们知道两个数相乘,质因子是相加的
- 所以设f[i][j][k]为到第i行j列第k个质因子转移显然
代码
1 #include<iostream>
2 using namespace std;
3 const long long mod=1000000009;
4 int f[1001][101][170],prime[1001],cnt;
5 bool vis[1001];
6 int n,kk;
7 int main ()
8 {
9 for (int i=2;i<=1000;i++)
10 if (!vis[i])
11 {
12 prime[++cnt]=i;
13 for (int j=i+i;j<=1000;j+=i)
14 vis[j]=1;
15 }
16 cin>>n>>kk;
17 for (int i=1;i<=n;i++)
18 for (int j=1;j<=cnt;j++)
19 {
20 long long now=prime[j],t=i/now,t1=0;
21 if (t==0) break;
22 while (t) t1=(t1+t)%mod,t/=now;
23 f[i][1][j]=t1%mod;
24 }
25 for (int i=2;i<=n;i++)
26 for (int j=2;j<=kk;j++)
27 for (int k=1;k<=cnt;k++)
28 f[i][j][k]=(f[i-1][j][k]+f[i][j-1][k])%mod;
29 long long ans=1;
30 for (int k=1;k<=cnt;k++)
31 ans=ans*(f[n][kk][k]+1)%mod;
32 cout<<ans;
33 }