GMOJ P3504 【运算符】

|

Description

定义新运算 “$!$” ，运算规则如下：

$a!b = a!(b-1) \times (a-1)!b ( a > 0,b > 0 )$
$a!b = 1 ( a = 0 )$
$a!b = a ( b = 0 )$

。

给你两个正整数 $n$ 和 $k$ ，现在请你求出 $n!k$ 的因子个数 $\mod (10^9+9)$ 。

$1\leq n\leq 1000,1 \leq k \leq 100$ 。

Solution

考虑使用 递推 来解题。

设 $f[i][j][k]$ 表示 $i ! j$ 分解质因数后的第 $k$ 个 质数 的指数的值，那显然有：

$f[i][j][k]=(f[i-1][j][k]+f[i][j-1][k])\mod(10^9+9)$

。

若一个数 $n=p_1^{k_1} \times p_2^{k_2} \times … \times p_m^{k_m}$ ，其中 $p_1$ ~ $p_m$ 均为质数，那么 $n$ 的因子个数为 $\prod_{i=1}^m (k_i+1)$ 。

所以我们可以得出答案等于 $(\prod_{i=1}^{n}(f[n][k][i]+1)) \mod;(10^9+9)$ 。

记得要中途取模！

时间复杂度 $O(nk)$，具体细节详见 代码 部分。

然后这道题目就做完了。

Code

1
#include<cstdio>
2
const int N=1e9+9;
3
int n,m,a[169],len;
4
int f[1001][101][169];
5
long long int ans=1;
6
bool bz[1001];
7
int main()
8
{
9
    scanf("%d%d",&n,&m);
10
    a[++len]=2;
11
    for(int i=3;i<=n;i+=2)
12
    {
13
        if(bz[i]==false)
14
        {
15
            a[++len]=i;
16
            for(int j=3;j<=n/i;j+=2)
17
            {
18
                bz[i*j]=true;
19
            }
20
        }
21
    }
22
    for(int i=1;i<=n;i++)
23
    {
24
        int x=i;
25
        for(int j=1;j<=len&&a[j]<=i;j++)
26
        {
27
            while(x%a[j]==0)x/=a[j],f[i][0][j]++;
28
        }
29
    }
30
    for(int i=1;i<=n;i++)
31
    {
32
        for(int j=1;j<=m;j++)
33
        {
34
            for(int k=1;k<=len;k++)
35
            {
36
                f[i][j][k]=(f[i-1][j][k]+f[i][j-1][k])%N;
37
            }
38
        }
39
    }
40
    for(int i=1;i<=len;i++)
41
    {
42
        ans=(ans*(f[n][m][i]+1))%N;
43
    }
44
    printf("%d",ans);
45
    return 0;
46
}