题目大意：有$n-1$个数为$2\sim n$，其中$n\leq 500$，两个人选数，要求两个人选的数中，每个人选的数都和另一个人选的所有数互质。问选的方法总数。
题解：状压$DP$，由于一个数$N$最多有一个大于$\sqrt{N}$的质因子，可以对小于等于$\sqrt{N}$的质因子和大于$\sqrt{N}$的分别考虑。
发现$\sqrt{500}$以内的质数只有$8$个。令$f_{i,j}$表示第一个人取了质数集合$i$，第二个人取了质数集合$j$的方案数。
再考虑大质数的情况。对所有的数，按照大质因子排序，然后令$g_{0/1,i,j}$表示两个人取的数中，第一个人取了质数集合$i$，第二个人取了质数集合$j$，且当前大质数集合由第一个人取或第二个人取的方案数。
最后令$f_{i,j}=g_{0,i,j}+g_{1,i,j}-f_{i,j}$，因为存在两人都不取的情况，被计算了两次，减去。
卡点：无
C++ Code：
#include#include #include #define P (1 << 8)#define maxn 510using namespace std;const int plist[8] = {2, 3, 5, 7, 11, 13, 17, 19};int n, p, f[P][P], g[2][P][P];int s[maxn], rem[maxn], rnk[maxn], ans;inline bool cmp(int a, int b) {return rem[a] < rem[b];}inline bool start(int i) {return rem[rnk[i]] == 1 || rem[rnk[i]] != rem[rnk[i - 1]];}inline bool end(int i) {return rem[rnk[i]] == 1 || rem[rnk[i]] != rem[rnk[i + 1]];}inline void update(int &a, int b) {a = (a + b) % p;}int main() { scanf("%d%d", &n, &p); for (int i = 2; i <= n; i++) { int tmp = i; for (int j = 0; j < 8; j++) { if (tmp % plist[j] == 0) { s[i] |= 1 << j; while (tmp % plist[j] == 0) tmp /= plist[j]; } } rem[i] = tmp; rnk[i] = i; } sort(rnk + 2, rnk + n + 1, cmp); rem[0] = 0; f[0][0] = 1; for (int i = 2; i <= n; i++) { if (start(i)) { memcpy(g[0], f, sizeof f); memcpy(g[1], f, sizeof f); } for (int j = P - 1; ~j; j--) { for (int k = P - 1; ~k; k--) { if (!(j & k)) { if ((k & s[rnk[i]]) == 0) update(g[0][j | s[rnk[i]]][k], g[0][j][k]); if ((j & s[rnk[i]]) == 0) update(g[1][j][k | s[rnk[i]]], g[1][j][k]); } } } if (end(i)) { for (int j = 0; j < P; j++) { for (int k = 0; k < P; k++) { f[j][k] = (1ll * g[0][j][k] + g[1][j][k] - f[j][k] + p) % p; if (i == n) update(ans, f[j][k]); } } } } printf("%d\n", ans); return 0;}