洛谷P2150 寿司晚宴

传送门

题目描述

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

在晚宴上，主办方为大家提供了 n−1n−1 种不同的寿司，编号 1,2,3,\ldots,n-11,2,3,…,n−1，其中第 ii 种寿司的美味度为 i+1i+1。（即寿司的美味度为从 22 到 nn）

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 xx 的寿司，小 W 品尝的寿司中存在一种美味度为 yy 的寿司，而 xx 与 yy 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 pp 取模）。注意一个人可以不吃任何寿司。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制
3 10000
输出 #1复制
9
输入 #2复制
4 10000
输出 #2复制
21
输入 #3复制
100 100000000
输出 #3复制
3107203

说明/提示

【数据范围】

勘误：0 < p \le 10^90<p≤10
9

上代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 505;
int n, mod, f[1 << 8][1 << 8], g[2][1 << 8][1 << 8];
pair<int, int> a[maxn];

inline int gi()
{
    
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int sum = 0;
    while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

const int maxp = 8;
const int p[8] = {
    
    2, 3, 5, 7, 11, 13, 17, 19
};

inline void inc(int &a, int b)
{
    
    a += b;
    if (a >= mod) a -= mod;
}

int main()
{
    
    n = gi(); mod = gi();
    for (int i = 2; i <= n; ++i) {
    
        int k = i;
        for (int j = 0; j < maxp; ++j)
            if (k % p[j] == 0) {
    
                a[i].second ^= 1 << j;
                while (k % p[j] == 0) k /= p[j];
            }
        a[i].first = k;
    }

    sort(a + 2, a + n + 1);
    f[0][0] = 1;
    for (int i = 2; i <= n; ++i) {
    
        if (i == 2 || a[i].first == 1 || a[i].first != a[i - 1].first) {
    
            memcpy(g[0], f, sizeof(g[0]));
            memcpy(g[1], f, sizeof(g[1]));
        }
        for (int s1 = (1 << maxp) - 1; s1 >= 0; --s1)
            for (int s2 = (1 << maxp) - 1; s2 >= 0; --s2) {
    
                if ((s2 & a[i].second) == 0) inc(g[0][s1 | a[i].second][s2], g[0][s1][s2]);
                if ((s1 & a[i].second) == 0) inc(g[1][s1][s2 | a[i].second], g[1][s1][s2]);
            }

        if (i == n || a[i].first == 1 || a[i].first != a[i + 1].first) {
    
            for (int s1 = (1 << maxp) - 1; ~s1; --s1)
                for (int s2 = (1 << maxp) - 1; ~s2; --s2) {
    
                    f[s1][s2] = g[0][s1][s2] + g[1][s1][s2] - f[s1][s2];
                    if (f[s1][s2] < 0) f[s1][s2] += mod;
                    if (f[s1][s2] >= mod) f[s1][s2] -= mod;
                }
        }

    }

    int ans = 0;
    for (int s1 = (1 << maxp) - 1; ~s1; --s1)
        for (int s2 = (1 << maxp) - 1; ~s2; --s2)
            if ((s1 & s2) == 0) inc(ans, f[s1][s2]);
    printf("%d\n", ans);

    return 0;
}