BZOJ 4197
题意:给定$n$,求出选择两个不相交集合$A,B$,不存在$d$使得$d|(x\in A), d|(y\in B)$的方案。
我们发现$n=500$以内质数小于$\sqrt n$的只有$8$个,我们考虑状压小质数当做背包容量,然后再用大质数(每个数只有最多一个)来分组做分组背包。
设$dp(S,T)$为选的集合分别是$S,T$的方案
每次大质数相同的一起转移,考虑转移时设$f(S,T,0/1)$表示大质数放$S$还是$T$的方案。
然后分别转移即可,$dp(S,T)=f(S,T,0)+f(S,T,1)-dp(S, T)$
没有大质数的可以处理完马上转移,具体看代码实现,比较简单
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL MO, dp[260][260], f[2][260][260];
int n;
int pri[10] = {2, 3, 5, 7, 11, 13, 17, 19};
struct data {int st, pri;} a[505];
bool cmp(data a, data b) {return a.pri < b.pri;}
void clean() {
}
int solve() {
clean();
cin >> n >> MO;
for (int i = 1; i < n; ++i) {
int tmp = i + 1;
for (int j = 2; j * j <= tmp; ++j) {
if (tmp % j == 0) {
for (int k = 0; k < 8; ++k) if (j == pri[k]) a[i].st |= (1 << k);
while (tmp % j == 0) tmp /= j;
}
}
if (tmp != 1) {
if (tmp > 19) a[i].pri = tmp;
else {
for (int k = 0; k < 8; ++k) if (tmp == pri[k]) a[i].st |= (1 << k);
}
}
}
sort(a + 1, a + n, cmp);
dp[0][0] = 1;
for (int i = 1; i < n; ++i) {
if (i == 1 || a[i].pri != a[i - 1].pri || a[i].pri == 0) memcpy(f[0], dp, sizeof dp), memcpy(f[1], dp, sizeof dp);
for (int S1 = 255; ~S1; --S1) {
for (int S2 = 255; ~S2; --S2) {
if (S1 & S2) continue ;
if (!(a[i].st & S2)) (f[0][S1 | a[i].st][S2] += f[0][S1][S2]) %= MO;
if (!(a[i].st & S1)) (f[1][S1][S2 | a[i].st] += f[1][S1][S2]) %= MO;
}
}
if (i == n - 1 || a[i].pri != a[i + 1].pri || a[i].pri == 0) {
for (int S1 = 255; ~S1; --S1) {
for (int S2 = 255; ~S2; --S2) {
if (S1 & S2) continue ;
dp[S1][S2] = ((f[0][S1][S2] + f[1][S1][S2] - dp[S1][S2]) % MO + MO) % MO;
}
}
}
}
LL ans = 0;
for (int S1 = 0; S1 <= 255; ++S1) {
for (int S2 = 0; S2 <= 255; ++S2) {
if (S1 & S2) continue ;
(ans += dp[S1][S2]) %= MO;
}
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}