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;
}