LibreOJ 2131.「NOI2015」寿司晚宴

神题神题,今天来玩几道状压题。

首先考虑若 \(n \le 20\) 怎么做:
显然记录一下质因子集合即可。

然而 \(n \le 500\),但是根据一些基本的数论知识,每个数最多只有一个超过 \(19\) 的质因子(下称大质因子)。
于是可以考虑每个数的大质因子预处理出来,然后把大质因子相同的放在一起处理。

具体地说,就是对于每个连续段,考虑把这个大质因子给小 G 或小 W,然后合并答案(注意不选大质因子的会被算两次,容斥掉)。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500;
const int P = 8;
const int prime[] = {0,2,3,5,7,11,13,17,19};
const int full = (1 << P) - 1;
int n;
long long mod,f[(1 << P) + 5][(1 << P) + 5],g[2][(1 << P) + 5][(1 << P) + 5],ans;
struct note
{
int s,w;
inline bool operator<(const note &o) const
{
return w < o.w;
}
} a[N + 5];
int main()
{
scanf("%d%lld",&n,&mod),f[0][0] = 1;
for(register int i = 2,v;i <= n;++i)
{
v = i;
for(register int j = 1;j <= P && v > 1;++j)
{
!(v % prime[j]) && (a[i - 1].s |= (1 << j - 1));
for(;!(v % prime[j]);v /= prime[j]);
}
a[i - 1].w = v;
}
sort(a + 1,a + n);
for(register int i = 1;i < n;++i)
{
if(a[i].w == 1 || (a[i].w ^ a[i - 1].w))
memcpy(g[0],f,sizeof g[0]),memcpy(g[1],f,sizeof g[1]);
for(register int j = full;~j;--j)
for(register int k = full;~k;--k)
if(!(j & k))
!(a[i].s & k) && (g[0][j | a[i].s][k] = (g[0][j | a[i].s][k] + g[0][j][k]) % mod),
!(a[i].s & j) && (g[1][j][k | a[i].s] = (g[1][j][k | a[i].s] + g[1][j][k]) % mod);
if(a[i].w == 1 || (a[i].w ^ a[i + 1].w))
for(register int j = full;~j;--j)
for(register int k = full;~k;--k)
f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k] + mod) % mod;
}
for(register int i = 0;i <= full;++i)
for(register int j = 0;j <= full;++j)
!(i & j) && (ans = (ans + f[i][j]) % mod);
printf("%lld\n",ans);
}