Luogu P2150 [NOI2015]寿司晚宴

题目链接：​​传送门​​

太难了太难了
题意就是问有多少种分案把一个到的排列分配为两组并使组间元素两两互质

首先我们只需要考虑根号内的质因子对答案的影响，因为根号外的因子最多出现一次，可以另外单独考虑
，内的素数只有个
所以我们可以通过状压来枚举他们所有的情况
但是大于的就要单独考虑了
因为
所以一个数不可能同时包含两个大于的相同质因子
也就是一个小于的数最多有个比大的质因子
那么就可以单独考虑将这个大质数放到哪一组中
下面用来表示将这个大质数放到了组中
更新的时候由于只能由上一位转移过来所以第一维可以直接压掉
就是第一组质数集合为第二组质数集合为的方案数
是全局的答案，是当前这个数的答案，就是~这些数
每次要让这两个数组互相更新
大质因子相同的一块统计答案，会减少额外的复杂度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int s, p;
  friend bool operator < (const node a, const node b) {
    return a.p < b.p; //让相同的大质数凑起来减少枚举量
  }
}e[A];
const int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
const int lim = (1 << 8);
int n, mod; ll f[A][A], g[A][A][2], ans;

int main(int argc, char const *argv[]) {
  cin >> n >> mod;
  for (int i = 2; i <= n; i++) {
    int t = i;
    for (int j = 0; j < 8; j++) {
      if (t % pri[j] == 0) {
        while (t % pri[j] == 0) t /= pri[j];
        e[i].s |= (1 << j); //质因子集合
      }
      e[i].p = t; //唯一的大质数
    }
  }
  sort(e + 2, e + n + 1); f[0][0] = 1;
  for (int i = 2; i <= n; i++) {
    if (e[i].p == 1 or e[i].p != e[i - 1].p) //换了大质数
      for (int j = 0; j <= lim; j++)
        for (int k = 0; k <= lim; k++)
          g[j][k][0] = g[j][k][1] = f[j][k]; //要更新当前的g数组
    for (int j = lim; j >= 0; j--)
      for (int k = lim; k >= 0; k--) { //看是否可以更新,也就是有无交集
        if ((e[i].s & k) == 0) g[j | e[i].s][k][1] = (g[j | e[i].s][k][1] + g[j][k][1]) % mod;
        if ((e[i].s & j) == 0) g[j][k | e[i].s][0] = (g[j][k | e[i].s][0] + g[j][k][0]) % mod;
      }
    if (e[i].p == 1 or e[i].p != e[i + 1].p)
      for (int j = lim; j >= 0; j--) //把求得的g数组赋给f
        for (int k = lim; k >= 0; k--) //最后要减去重复算得的f,因为两个集合都不选的情况算了两遍
          f[j][k] = (g[j][k][0] + g[j][k][1] - f[j][k] + mod) % mod;
  }
  for (int i = 0; i <= lim; i++)
    for (int j = 0; j <= lim; j++)
      if (!(i & j)) ans = (ans + f[i][j]) % mod;
  cout << ans << endl;
}