「BZOJ4197」[Noi2015]寿司晚宴

Description

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

在晚宴上,主办方为大家提供了 n1n−1 种不同的寿司,编号 1,2,3,1,2,3, \cdots , n1n−1 ,其中第 ii 种寿司的美味度为 i+1i+1 (即寿司的美味度为从 22nn)。

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

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

Input

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

Output

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

Sample Input

1
3 10000

Sample Output

1
9

HINT

2n500, 0<p10000000002 \leq n \leq 500, \ 0 < p \leq 1000000000

Solution

force

3030分做法:fi,s1,s2f_{i,s1,s2}表示选到第ii个数字,AA所有寿司的质因数的并的状态为s1s1,BB的状态是s2s2.

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

ll f[2][1<<11][1<<11];
ll p;
int n;
int b[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29};
int main() {
f[0][0][0] = 1;
n = read(), p = read();
int t = 0;
for(int i = 2; i <= n; ++i) {
int k = 0, y = i;
for(int j = 0; y > 1; ++j)
if(y % b[j] == 0) {
while(y % b[j] == 0) {
y /= b[j];
}
k += (1 << j);
}
t ^= 1;
memset(f[t], 0, sizeof f[t]);
for(int s1 = 0; s1 < 2048; ++s1)
for(int s2 = 0; s2 < 2048; ++s2) if(!(s1 & s2)){
f[t][s1][s2] += f[t ^ 1][s1][s2];
if(((s1 | k) & s2) == 0) f[t][s1 | k][s2] += f[t ^ 1][s1][s2];
if(((s2 | k) & s1) == 0) f[t][s1][s2 | k] += f[t ^ 1][s1][s2];
f[t][s1][s2] %= p;
}
}
int ans = 0;
for(int i = 0; i < 2048; ++i)
for(int j = 0; j < 2048; ++j)
if(!(i & j)) ans = (ans + f[t][i][j]) % p;
writeln(ans);
return 0;
}

std

发现n>500=22.360679775n>\sqrt{500}=22.360679775的质因数只有一个。
我们对于[2,n][2,n]每一个数按照最大质因数排序。
对于最大质因数pi>22p_i>22的一大段,只允许要么AA取,或者bb取,能不能同时取,所以可以记录g1i,s1,s2,g2i,s1,s2g1_{i,s1,s2},g2_{i,s1,s2}分别表示AA所有得到寿司的质因子qi<=22q_i<=22的状态为s1s1BB的状态s2s2。只要累加就行了,s1,s2s1,s2不用改变。
最后把g1,g2g1,g2合并给答案ff数组

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
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 510;
ll p;
int n;
int b[] = {2, 3, 5, 7, 11, 13, 17, 19};
ll f[2][300][300], g1[2][300][300], g2[2][300][300];
int t;
struct T {
int x;
int v;
int s;
int tmp;
void init() {
for(int i = 7;~i;--i)
if(x % b[i] == 0) {
while(x % b[i] == 0) x /= b[i];
s ^= (1 << i);
if(v == 0) v = b[i];
}
if(!v || x > 1)
v = x;
}
}a[N];
bool cmp(T _x, T _y) {
return _x.v > _y.v;
}
int main() {
n = read(), p = read();
--n;
for(int i = 1; i <= n; ++i) {
a[i].x = i + 1;
a[i].init();
a[i].tmp = i + 1;
}
sort(a +1, a + 1 + n, cmp);
f[t][0][0] = 1;
for(int i = 1, j; i <= n; i = j) {
j = i;
while(a[j].v == a[i].v) ++j;
if(a[i].v <= 19) {
for(int k = i; k < j; ++k) {
t ^= 1;
memset(f[t], 0, sizeof f[t]);
for(int x = 0; x < 256; ++x)
for(int y = 0; y < 256; ++y) if(!(x & y)) {
f[t][x][y] += f[t ^ 1][x][y];
if(((x | a[k].s) & y) == 0) f[t][x | a[k].s][y] += f[t ^ 1][x][y];
if(((y | a[k].s) & x) == 0) f[t][x][y | a[k].s] += f[t ^ 1][x][y];
f[t][x][y] %= p;
}
}
} else {
bool o = 0;
memmove(g1[o], f[t], sizeof g1[o]);
memmove(g2[o], f[t], sizeof g2[o]);
t ^= 1;
memset(f[t], 0, sizeof f[t]);
for(int k = i; k < j; ++k) {
o ^= 1;
memset(g1[o], 0, sizeof g1[o]);
memset(g2[o], 0, sizeof g2[o]);
for(int x = 0; x < 256; ++x)
for(int y = 0; y < 256; ++y) if(!(x & y)) {
g1[o][x][y] += g1[o ^ 1][x][y];
g2[o][x][y] += g2[o ^ 1][x][y];
if(((x | a[k].s) & y) == 0) g1[o][x | a[k].s][y] += g1[o ^ 1][x][y];
if(((y | a[k].s) & x) == 0) g2[o][x][y | a[k].s] += g2[o ^ 1][x][y];
g1[o][x][y] %= p;
g2[o][x][y] %= p;
}
}
for(int x = 0; x < 256; ++x)
for(int y = 0; y < 256; ++y) if(!(x & y)) {
f[t][x][y] = g1[o][x][y] + g2[o][x][y] - f[t ^ 1][x][y];
f[t][x][y] %= p;
}
}
}
ll ans = 0;
for(int x = 0; x < 256; ++x)
for(int y = 0; y < 256; ++y) if(!(x & y))
ans = (ans + f[t][x][y]) % p;
ans += p;
ans %= p;
writeln(ans);
return 0;
}