[NOI2015]寿司晚宴

Posted on Edited on In Word count in article: 651 Reading time ≈ 2 mins.
又难又好玩

[NOI2015]寿司晚宴

题目大意

你有数集 \(\{1,2,3\cdots n-1\}\) ，问你把这些数分派到两个集合中（可以是空集）且这两个集合的没有公共的素因子的方案数

分析

这个是可以暴力枚举的，期望 \(30\) 分？

考虑把所有数的素因子列出来，可以发现，对于每个数，它一定不会有两个及以上大于 \(22\) 的素因子

那么就是可以这样理解，可以把所有的小于 \(22\) 的素数列举出来，那么就只有 \(8\) 个，这部分就可以状压，那么就可以单独用一维来处理素因子大于 \(22\) 的部分

听上去十分的简单，但是，这个必须保证所有有大于 \(22\) 的素因子的数在同一个集合中，所以要用 \(f_1\)表示这类数在第一个集合中，用 \(f_2\) 表示这一类数在第二个集合中

然后在用 \(f\) 表示上一种状态答案，然后每次大素数发生改变的时候，就可以更新一下所有的信息 （要用一个简单容斥）

然后这样看上去貌似就不难了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar())      {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, m;
const int p[10] = {2, 3, 5, 7, 11, 13, 17, 19};

struct Node
{
    int sta, res;

    Node () {}

    Node(int val) {
        sta = res = 0;
        for (int i = 0; p[i]; ++i) {
            if (val % p[i]) continue;
            sta |= 1 << i;
            while (!(val % p[i])) val /= p[i];
        }
        if (val > 1) res = val;
    }

    bool operator < (const Node &T) const {
        return res < T.res;
    }
}a[505];

int f[265][265], f1[265][265], f2[265][265];

inline int add(int x, int y) 
{
    const int t = x + y;
    if (t >= m) return t - m;
    return t; 
 }

int main()
{
    n = __read(), m = __read();
    for (int i = 2; i <= n; ++i) a[i - 1] = Node(i);
    f[0][0] = 1;
    sort (a + 1, a + n);    
    for (int i = 1; i < n; ++i) {
        if (i == 1 || a[i].res ^ a[i - 1].res || !a[i].res) {
            memcpy (f1, f, sizeof f1);
            memcpy (f2, f, sizeof f2);
        }

        for (int j = 255; ~j; --j)
            for (int k = 255; ~k; --k) {
                if (j & k) continue;
                const int t = a[i].sta;
                if (!(t & j)) f2[j][k | t] = add(f2[j][k | t], f2[j][k]);
                if (!(t & k)) f1[j | t][k] = add(f1[j | t][k], f1[j][k]);
            }

        if (i == n - 1 || a[i].res ^ a[i + 1].res || !a[i].res) {
            for (int j = 0; j <= 255; ++j)
                for (int k = 0; k <= 255; ++k) {
                    if (j & k) continue;
                    f[j][k] = add(f1[j][k], add(f2[j][k], m - f[j][k]));
                }
        }
    }

    ll ans(0);
    for (int i = 0; i <= 255; ++i)
        for (int j = 0; j <= 255; ++j)
            if (!(i & j)) ans = add(ans, f[i][j]);
    printf ("%lld\n", ans);
}