BZOJ 4197 - [Noi2015]寿司晚宴

#dp #位运算
Published on 2016-05-11

题目地址

描述

为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。

在晚宴上,主办方为大家提供了 种不同的寿司，编号 ，其中第 ii 种寿司的美味度为 i+1i+1 （即寿司的美味度为从 22 到 nn）。
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 xx 的寿司，小 W 品尝的寿司中存在一种美味度为 yy 的寿司，而 xx 与 yy 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 pp 取模）。注意一个人可以不吃任何寿司。

分析

逐步分析。
30分：
n≤30n\le 30，一个明显的思路在于枚举某个人选哪些数，然后再统计答案，这样显然是爆炸的。
为什么会爆炸呢？原因是我们没有抓住互质的实质，互质的实质在于没有相同的素因子，数很多，但 30 以内的素数却只有区区 10 个，因此我们可以考虑状态压缩dp统计答案。将每个数分解质因数，然后压成二进制位 aia_i。
设 f[i][s1][s2]f[i][s_1][s_2] 为考虑前 ii 个数，第一个人选择的素因子集合为 s1s_1，第二个人选择的素因子集合为 s2s_2 的方案数。
那么状态是比较容易刷表转移的:

答案就是 ∑s1∪s2=∅f[n][s1][s2]\sum\limits_{s_1\cup s_2 = \emptyset}f[n][s_1][s_2]，我们注意到只要 ，都是不会被统计进答案的，所以我们在代码中加入判断来避免过多的取模操作。
另一个非常重要的优化就是压缩掉第一维，可以采用 2 个数组来交替滚动，但是在 01 背包中常用的方法就是使用一个数组，倒序计算来达到一样转移效果，这一点在后面反复体现。

100分：
让我们来看看为什么刚刚的做法不生效了，原因是 500 以内的素数太多了！状态开不下。注意到一个数 nn 只可能有一个大于 n\sqrt n 的素因子，所以我们单独考虑有大于 n\sqrt n 素因子的数。而 500=22.3..\sqrt {500} = 22.3..，只有区区 8 个素数。
我们先把没有大于 n\sqrt n 素因子的数抽出来做一次dp，就得到 f[s1][s2]f[s_1][s_2] 为考虑所有没有大于 n\sqrt n 素因子的数，第一个人选择的素因子集合为 s1s_1，第二个人选择的素因子集合为 s2s_2 的方案数。
还有剩下有大于 n\sqrt n 素因子的数怎么办？
考虑素因子 zz，所有具有素因子 zz 的数构成集合 szs_z，那么 szs_z 中所有元素要么都不选，否则只能由一个人选（可任意选），所以我们对这个集合单独拿出来 dp。

设 g(∣sz∣)[k][s1][s2]g(\mid s_z \mid)[k][s_1][s_2] 为第 k 个人来选这个集合，第一个总共选择的素因子集合为 s1s_1，第二个人总共选择的素因子集合为 s2s_2 的方案数，括号里的一维显然可以像刚刚那样压缩掉。
则初始 g[k][s1][s2]=f[s1][s2]g[k][s_1][s_2] = f[s_1][s_2]，转移是非常类似的（aia_i 是集合 szs_z 的第 ii 个元素拥有的质因子集合）：

这个集合dp完之后，反过来更新 ff 的答案（毕竟多了一些数嘛）：

f[s1][s2]=(g[0][s1][s2]+g[1][s1][s2]−f[s1][s2])modpf[s_1][s_2] = (g[0][s_1][s_2] + g[1][s_1][s_2] - f[s_1][s_2]) \bmod p

减 f[s1][s2]f[s_1][s_2] 的意思是两个人都不选的这个集合的数的情况被统计了 2 次。
继续做剩下的集合即可，

不难发现其实没有大于 n\sqrt n 素因子的数完全可以看作只有一个元素的集合，所以完全可以合并在一起 dp，非常简洁。

总结：

  1. 要发现问题的实质，比如互质实际上是没有相同的素因子。
  2. 学会用分类讨论来减少大量废状态。

代码

//  Created by Sengxian on 5/11/16.
//  Copyright (c) 2016年 Sengxian. ALL rights reserved.
//  BZOJ 4197 NOI 2015 D1t3
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
    return n;
}

const int maxp = 8, maxn = 500 + 3;
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, modu, f[1 << maxp][1 << maxp], g[2][1 << maxp][1 << maxp];

typedef pair<int, int> state;
state sts[maxn];

inline int mod(int x) {
    return (x % modu + modu) % modu;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), modu = ReadInt();
    for (int i = 2; i <= n; ++i) {
        sts[i].second = 0;
        int t = i;
        for (int j = 0; j < maxp; ++j)
            if (t % primes[j] == 0) {
                sts[i].second += 1 << j;
                while (t % primes[j] == 0) t /= primes[j];
            }
        sts[i].first = t;
    }
    sort(sts + 2, sts + 2 + n - 1);
    f[0][0] = 1;
    for (int i = 2; i <= n; ++i) {
        if (i == 2 || sts[i].first == 1 || sts[i].first != sts[i - 1].first) { //一个新的块，一个块中的所有元素只能被至多一个人选（且是同一人！
            memcpy(g[0], f, sizeof f);
            memcpy(g[1], f, sizeof f);
        }
        for (int k = 0; k < 1; ++k)
            for (int s1 = (1 << maxp) - 1; s1 >= 0; --s1)
                for (int s2 = (1 << maxp) - 1; s2 >= 0; --s2) {
                    if ((s2 & sts[i].second) == 0) (g[0][s1 | sts[i].second][s2] += g[0][s1][s2]) %= modu;
                    if ((s1 & sts[i].second) == 0) (g[1][s1][s2 | sts[i].second] += g[1][s1][s2]) %= modu;
                }
        if (i == n || sts[i].first == 1 || sts[i].first != sts[i + 1].first) {//结束块，用 g 去更新 f
            for (int s1 = (1 << maxp) - 1; s1 >= 0; --s1)
                for (int s2 = (1 << maxp) - 1; s2 >= 0; --s2)
                    f[s1][s2] = mod(g[0][s1][s2] + g[1][s1][s2] - f[s1][s2]); //注意两个人都不取算了两次，要减去！
        }
    }
    int ans = 0;
    for (int s1 = 0; s1 < (1 << maxp); ++s1)
        for (int s2 = 0; s2 < (1 << maxp); ++s2)
            if ((s1 & s2) == 0) (ans += f[s1][s2]) %= modu;
    printf("%d\n", ans);
    return 0;
}
APIO 2016 - 最大差分