DeepSeek LeetCode 3671. 子序列美丽值求和 Java实现

这道题需要计算所有“严格递增”且“GCD恰好为g”的子序列对答案的贡献。直接枚举所有子序列会超时所以核心思路是容斥原理 树状数组优化DP。算法思路1. “至少”变“恰好”先计算 cnt[g]表示子序列元素都是g的倍数即GCD“至少”为g的严格递增子序列数量。然后从大到小用容斥exact[g] cnt[g] - exact[2g] - exact[3g] - ...得到GCD恰好为g的数量。2. 计算 cnt[g]对每个可能的 g只看数组中 g 的倍数。用树状数组Fenwick Tree维护以某个值结尾的严格递增子序列个数。遍历这些倍数 x查询所有小于 x 的结尾的累计和 sum则 dp[x] sum 1自成一个子序列并累加到 cnt[g]。3. 汇总答案最终 answer sum(g * exact[g])。Java实现这里提供一个基于上述逻辑、使用树状数组优化的Java版本。javaclass Solution {private static final int MOD 1_000_000_007;public int totalBeauty(int[] nums) {int maxNum 0;for (int v : nums) maxNum Math.max(maxNum, v);// 1. 按因子分组groups[d] 存储 nums 中所有 d 的倍数ListInteger[] groups new List[maxNum 1];for (int i 1; i maxNum; i) groups[i] new ArrayList();for (int x : nums) {// 枚举 x 的所有因子 d并把 x 放入 groups[d]for (int d 1; d * d x; d) {if (x % d 0) {groups[d].add(x);if (d * d x) groups[x / d].add(x);}}}// cnt[g] 存储 GCD 至少为 g 的严格递增子序列数量long[] cnt new long[maxNum 1];// 2. 对每个可能的 g用树状数组计算 cnt[g]for (int g maxNum; g 1; g--) {ListInteger list groups[g];if (list.isEmpty()) continue;// 坐标压缩值 range maxNum / g将 x 映射到 x / g范围 1 ~ maxNum/gFenwick bit new Fenwick(maxNum / g 1);for (int x : list) {int idx x / g; // 索引从 1 开始// 查询以严格小于 x 的元素结尾的子序列总数long prev bit.query(idx - 1);// dp: 当前 x 作为末尾的新增子序列数前面的子序列追加 x或自成一派long dp (prev 1) % MOD;// 累加到 cnt[g]cnt[g] (cnt[g] dp) % MOD;// 更新树状数组bit.update(idx, dp);}}// 3. 容斥从大到小减去倍数的情况得到 GCD 恰好为 g 的数量long[] exact new long[maxNum 1];long ans 0;for (int g maxNum; g 1; g--) {long val cnt[g];for (int multiple g * 2; multiple maxNum; multiple g) {val (val - exact[multiple] MOD) % MOD;}exact[g] val;ans (ans (long) g * val) % MOD;}return (int) ans;}// 树状数组类支持单点更新、前缀查询class Fenwick {int n;long[] tree;Fenwick(int n) {this.n n;this.tree new long[n 1];}void update(int idx, long delta) {while (idx tree.length) {tree[idx] (tree[idx] delta) % MOD;idx idx -idx;}}long query(int idx) {long res 0;while (idx 0) {res (res tree[idx]) % MOD;idx - idx -idx;}return res;}}}复杂度分析· 时间复杂度O(N * sqrt(M) M * log M)其中 N 是数组长度M 是数组最大值。枚举因子和容斥是调和级数相关操作整体可在限定条件下运行。· 空间复杂度O(M N * sqrt(M))主要用于存储分组和树状数组。