题解

算法分析

本题是一个典型的 状态压缩动态规划 问题，结合了 质因数分解 和 集合划分 的思想，属于 数论 + 动态规划 的复合题型。

问题本质

我们需要将美味度为 $2$ 到 $n$ 的寿司分配给两个人（小 G 和小 W），要求不存在 $x$ 在 G 中、$y$ 在 W 中且 $\gcd(x,y) > 1$ 的情况。

核心思路

1. 质因数分类：

   • 只考虑前 $8$ 个小质数：$2,3,5,7,11,13,17,19$
   • 对于每个数，如果包含大于 $19$ 的大质因子，则按大质因子分组处理

2. 状态表示：

   • 使用 $8$ 位二进制数表示包含的小质因子集合
   • $f[i][j]$ 表示 G 的小质因子集合为 $i$，W 的小质因子集合为 $j$ 的方案数
   • 要求 $i \cap j = \emptyset$（即没有公共质因子）

3. 分组处理：

   • 先处理不含大质因子的数（大质因子为 $1$）
   • 再对每个大质因子组分别处理，使用 背包合并 的思想

算法标签

• 状态压缩动态规划
• 质因数分解
• 集合划分
• 数论 - 质数性质

关键代码解析

// 前8个小质数
ll t[] = {2, 3, 5, 7, 11, 13, 17, 19};

// 计算数x包含的小质因子集合
ll to(ll x) {
    ll o = 0;
    for (ll i = 7; i >= 0; i--)
        o = o * 2 + (x % t[i] == 0);
    return o;
}

// 主DP过程
F(i, 2, n) {
    ll x = i;
    // 提取大质因子
    for (ll j : t) while (x % j == 0) x /= j;
    v[x].push_back(i);  // 按大质因子分组
}

// 处理不含大质因子的数
for (ll x : v[1]) {
    ll o = to(x);
    // 更新f[i][j]：可以选择给G或给W
}

// 处理含大质因子的组
F(p, 23, n) if (v[p].size()) {
    // 分别计算给G和给W的方案
    // 最后合并：f = g + h - f（容斥）
}

状态转移

对于每个数 $x$：

• 如果给 G：要求 $x$ 的质因子集合与 W 的当前集合无交集
• 如果给 W：要求 $x$ 的质因子集合与 G 的当前集合无交集

对于大质因子组：同一组的数不能同时分给两个人（因为会有公共的大质因子），所以分别计算全给 G 和全给 W 的方案，再用容斥合并。

时间复杂度

• 质因数分解：$O(n \log n)$
• 状态转移：$O(n \times 2^{16})$（状态数 $256 \times 256$）
• 总体复杂度：$O(n \times 2^{16})$，能够处理 $n \leq 500$ 的数据规模

空间复杂度

• $O(2^{16})$，用于存储 DP 状态

总结

本题通过将质因数分为小质数和大质数，利用状态压缩高效处理约束条件，是状态压缩 DP 的经典应用。关键在于发现只有前 $8$ 个小质数需要压缩状态，大质数可以通过分组处理来保证同一组的数不会产生冲突。