[中山A组20180814]计算

发表于 更新于

标签

数学 + dpdp + 计数计数

思路

对于任意一组 xx 满足 ∏i=12mxi≤nm\prod_{i = 1}^{2m}x_i \leq n^m , 都一定存在 ∏i=12mnxi≥nm\prod_{i=1}^{2m}\frac{n}{x_i}\geq n^m , 显然这两类数列之间是一一对应的. 设 s1s_1 表示 ∏i=12mxi≤nm\prod_{i = 1}^{2m}x_i \leq n^m 的数列数量 , s2s_2 表示 ∏i=12mxi=nm\prod_{i = 1}^{2m}x_i =n^m 的数列数量 , s3s_3 表示 ∏i=12mxi≥nm\prod_{i = 1}^{2m}x_i \geq n^m 的数列数量 .
有 s1=s3s_1 = s_3 , s1+s3−s2=d(n)2ms_1 + s_3 - s_2 = d(n)^{2m} , 所以有 s1=d(n)2m+s22s_1 = \frac{d(n)^{2m} + s_2}{2} .

所以我们只需要求出 s2s_2 就可以求出 s1s_1 了.

关于求 s2s_2 , 对 nn 质因数分解, 发现 nn 的每一个质因数 pp 都是相互独立的. 我们只要分别求出然后乘起来就行了, 对于一个 pp , 设 cc 表示 nn 的质因数 pp 的个数. 所以我们要求的就是满足 ∑i=12mai=c∗m,0≤aj≤c,aj∈Z\sum_{i=1}^{2m}a_i = c * m , 0 \leq a_j \leq c , a_j \in Z 的 aa 序列的个数.

这个东西可以 dpdp 求. 设 f[i][j]f[i][j] 表示 dpdp 到第 ii 个数, 当前 aa 的和为 jj 的方案数. 有 f[i][j]=∑k=0cf[i−1][j−k]f[i][j] = \sum_{k = 0}^{c} f[i - 1][j - k] 最后 f[2m][c∗m]f[2m][c * m] 就答案.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int mod = 998244353;
const int N = 310;
int n, m;
int f[N][N * 30];
int p[N], c[N], tot;
int d;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int ans = 1;

int dp(int c) {
    for (int i = 0; i <= 2 * m; ++i) {
        for (int j = 0; j <= m * c; ++j) {
            f[i][j] = 0;
        }
    }
    f[0][0] = 1;
    for (int i = 1; i <= 2 * m; ++i) {
        for (int j = 0; j <= m * c; ++j) {
            for (int k = 0; k <= min(c, j); ++k) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
            }
        }
    }
    return f[2 * m][m * c];
}

signed main() {
    scanf("%lld%lld", &n, &m);
    d = 1;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            p[++tot] = i;
            while (n % i == 0) n /= i, ++c[tot]; 
            d = d * (c[tot] + 1) % mod;
        }
    }
    if (n > 1) p[++tot] = n, ++c[tot], d = d * 2 % mod;
    for (int i = 1; i <= tot; ++i) {
        ans = ans * dp(c[i]) % mod;
    }
    printf("%lld\n", (qpow(d, 2 * m) + ans) % mod * qpow(2, mod - 2) % mod);
    return 0;
}

总结

用 s2s_2 表示 s1s_1 的那一步很妙. 尤其是通过数列间的一一对应来证明 s1=s3s_1 = s_3 .

有时候恰好会比至多和至少好求, 且至多的方案数等于至少的方案数, 就可以通过这种方法来求解