破晓的知识屋
0%

第301场周赛-808名-3题

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

第 301 场周赛 - 力扣（LeetCode）

1657468677496

第四题要点：

  1. 我直接站在n（10^4)的角度去推演和动规， 却忘记了必须是连续被整除的条件。

    即使n=100， maxValue=32， 实际上大部分都是重复的数字， 连续被整除的关键点最长只有1->2->4->8->16->32， 这是最长的6个关键点， 剩下的就是从n=100中选6个放入关键点，其他数字保持一致。

  2. 因此dp关键点方案数的数组的定义不是dp[n][maxValue], 而是dp[log2(maxValue)][maxValue]

  3. 基于dp和排列组合方式， 联合计算

  4. 排列组合方式求解。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public static int MOD = 1000000007;

// c[n][m],数组下标就是m，n-1是固定的了
long[][] c;

// 关键点1：预处理的话，如果C（n,m)的m比较小，就用杨辉三角来预处理，记住杨辉三角特点，纵轴是n，横轴是m
public void getC(int n, int m) {
    c = new long[n+1][m+1];
    for (int i = 1;i<=n;i++) {
        c[i][0] = 1;
        // 注意这里判断
        if (i <=m) {
            c[i][i] = 1;
        }
        for (int j = 1;j<m && j < i;j++) {
            c[i][j] = c[i-1][j-1] + c[i-1][j];
            c[i][j] %= MOD;
        }
    }
}


public int idealArrays(int n, int maxValue) {
    Set<Integer>[] divNums = new Set[maxValue+1];
    for (int i = 0;i<=maxValue;i++) {
        divNums[i]= new HashSet<>();
    }

    for (int value = 2;value<=maxValue;value++) {
        divNums[value].add(1);
        // 关键点：求除数，只需要根号(value)即可求解出来，不需要遍历整个value
        for (int div = 2; div  * div <= value;div++) {
            if (value % div == 0) {
                // 注意加上value/div
                divNums[value].add(div);
                divNums[value].add(value/div);
            }
        }
    }

    // 如何快速求log2?
    // 关键点：x->y->z->maxValue， 最大变化长度为log2(mavValue)，其他数字全是相同的
    // 因此不需要以n做动态规划
    int maxDivCount = 0;
    int value = maxValue;
    while (value > 0) {
        value /= 2;
        maxDivCount++;
    }

    long[][] dp = new long[maxDivCount+1][maxValue+1];

    // 以变换点个数做数组长度进行动态规划
    for (value = 0; value <=maxValue;value++) {
        for (int i = 1; i <=maxDivCount;i++) {
            if (i==1) {
                dp[i][value] = 1;
                continue;
            }

            for (int div : divNums[value]) {
                dp[i][value] += dp[i-1][div];
                dp[i][value] %= MOD;
            }
        }
    }

    // 组合数
    getC(n-1, maxDivCount);

    long sum = 0;
    for (value = 1;value <= maxValue;value++) {
        for (int divCount = 1; divCount <=maxDivCount;divCount++) {
            // value作为末尾点，长度为divCount，不相同时的方案数，  乘上(n-1)里面选(divCount-1）的组合数
            sum += c[n-1][divCount-1] * dp[divCount][value];
            sum %= MOD;
        }
    }
    return (int)sum;
}