bzoj 4197 [Noi2015]寿司晚宴

Description

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

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

Input

输入文件的第 1 行包含 2 个正整数 n,p，中间用单个空格隔开，表示共有 n 种寿司，最终和谐的方案数要对 p 取模。

Output

输出一行包含 1 个整数，表示所求的方案模 p 的结果。

Sample Input

3 10000

Sample Output

9

HINT

2≤n≤500

0< p≤1000000000

题解

看dalao的题解吧。。

记得这上面有最好的线性基的教程= =

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> Pair;
const int P = 8, N = 510, pr[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, mod, f[1 << P][1 << P], g[2][1 << P][1 << P];
long long ans;
Pair st[N];
main() {
    scanf("%d%d", &n, &mod);
    for (int i = 2; i <= n; ++i) {
        st[i].second = 0;
        int t = i;
        for (int j = 0; j < P; ++j)
            if (t % pr[j] == 0) {
            st[i].second |= 1 << j;
            while (t % pr[j] == 0) t /= pr[j];
        }
        st[i].first = t;
    }
    sort(st + 2, st + 1 + n);
    f[0][0] = 1;
    for (int i = 2; i <= n; ++i) {
        if (i == 2 || st[i].first == 1 || st[i].first != st[i - 1].first)
            memcpy(g[0], f, sizeof f), memcpy(g[1], f, sizeof f);
        for (int s1 = (1 << P) - 1; s1 >= 0; --s1)
            for (int s2 = (1 << P) - 1; s2 >= 0; --s2) {
                if ((s2 & st[i].second) == 0) (g[0][s1 | st[i].second][s2] += g[0][s1][s2]) %= mod;
                if ((s1 & st[i].second) == 0) (g[1][s1][s2 | st[i].second] += g[1][s1][s2]) %= mod;
            }
        if (i == n || st[i].first == 1 || st[i].first != st[i + 1].first)
            for (int s1 = (1 << P) - 1; s1 >= 0; --s1)
                for (int s2 = (1 << P) - 1; s2 >= 0; --s2)
                    f[s1][s2] = (long long)((g[0][s1][s2] + g[1][s1][s2] - f[s1][s2]) % mod + mod) % mod;
    }
    for (int s1 = 0; s1 < (1 << P); ++s1)
        for (int s2 = 0; s2 < (1 << P); ++s2)
            if ((s1 & s2) == 0) ans += 1ll * f[s1][s2], ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
}