P2150-[NOI2015]寿司晚宴
题目:
题目描述:
为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。
在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1, 2, 3, \ldots, n-1$，其中第种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。
输入格式:
输入文件的第 $1$ 行包含 $2$ 个正整数 $n, p$ 中间用单个空格隔开，表示共有 $n$ 种寿司，最终和谐的方案数要对 $p$ 取模。
输出格式:
输出一行包含 $1$ 个整数，表示所求的方案模 $p$ 的结果。
样例:
样例输入1:
样例输出1:
样例输入2:
样例输出2:
样例输入3:
样例输出3:
思路:
实现:
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
| #include "ybwhead/ios.h"
int n;
long long mod;
const int maxn = 5e2 + 10;
// int a[maxn];
int p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 0};
struct node
{
int big, S;
node() {}
node(int vv)
{
int i, tmp = vv;
big = -1;
S = 0;
for (i = 1; i <= 8; i++)
{
if (tmp % p[i])
continue;
S |= (1 << (i - 1));
while (tmp % p[i] == 0)
tmp /= p[i];
}
if (tmp != 1)
big = tmp;
}
friend bool operator<(node a, node b)
{
return a.big < b.big;
}
} a[maxn];
long long dp[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
long long pl(long long x, long long y)
{
x += y;
return x >= mod ? x - mod : x;
}
int main()
{
yin >> n >> mod;
for (int i = 2; i <= n; i++)
{
a[i - 1] = (node){i};
}
sort(a + 1, a + n);
dp[0][0] = f[0][0] = g[0][0] = 1;
for (int i = 1; i < n; i++)
{
for (int j = 255; j >= 0; j--)
{
for (int k = 255; k >= 0; k--)
{
if (j & k)
continue;
if ((a[i].S & j) == 0)
g[j][k | a[i].S] = pl(g[j][k | a[i].S], g[j][k]);
if ((a[i].S & k) == 0)
f[j | a[i].S][k] = pl(f[j | a[i].S][k], f[j][k]);
}
}
if (i == n - 1 || a[i].big != a[i + 1].big || a[i].big == -1)
{
for (int j = 0; j < 256; j++)
for (int k = 0; k < 256; k++)
if ((j & k) == 0)
dp[j][k] = pl(f[j][k], pl(g[j][k], mod - dp[j][k]));
memcpy(f, dp, sizeof(f));
memcpy(g, dp, sizeof(g));
}
}
long long ans = 0;
for (int j = 0; j < 256; j++)
for (int k = 0; k < 256; k++)
if ((j & k) == 0)
ans = pl(ans, dp[j][k]);
yout << ans << endl;
return 0;
}
|