知识点：状压 DP

原题面：Loj Luogu

---

扯

题目中的一句话：
寿司的美味度为从 \(2\) 到 \(n\)。

什么是良心出题人？
这就是良心出题人！

---

题意简述

给定 \(n,p\)，求：从 \(2\sim n\) 取出两个集合（可以为空），使得分属两个集合中的数均互质的方案的数量 \(\bmod p\)。
\(1\le n\le 500\)，\(1\le p\le 10^{10}\)。
时间 1s，空间 128M。

---

分析题意

30pts

注意以下讨论均在 \(\pmod{p}\) 下展开。

定义数集 \(S\) 中的数质因数分解后的质数集为 \(\operatorname{P}(S)\)。
显然对于集合 \(S1,S2\)，分属两集合中的数均互质的充要条件是 \(\operatorname{P}(S1) \cap \operatorname{P}(S2) = \varnothing\)。

考虑对于每一个质数集 \(\operatorname{P}(S)\)，求得其对应的质因数分解的集合 \(S\) 的个数。
又 \(n\le 30\)，质数仅有 \(10\) 个，考虑状压 DP。

设 \(f_{i,\operatorname{P}(S)}\) 表示，由 \(1\sim i\) 组成的数集 \(S\) 中，\(\operatorname{P}(S)=i\) 的个数。

对于 \(f\)，转移时使用刷表法，考虑加入数字 \(i\) 的影响，枚举质数集合 \(S\)，则有：

\[f_{i,S|\operatorname{P}(\{i\})} = f_{i,S|\operatorname{P}(\{i\})} + f_{i-1,S} \]

统计答案时枚举两方所选质数集合 \(S1,S2\)。当 \(S1\cap S2 = \varnothing\) 时，则有：

\[ans = ans + (f_{n,S1} \times f_{n,S2}) \]

直接做空间会爆炸，需要滚动数组优化一下。
总时间复杂度 \(O(n\times 2^{10} + 2^{20})\)。

---

100pts

直接存质数集合存不下了。

地球人都知道整数 \(i\) 至多只有一个大于 \(\sqrt {i}\) 的质因子。
相同的质因子互相冲突，考虑将 \(i\in [1,n]\) 按含有的大于 \(\sqrt {i}\) 的质因子进行划分，对每一数段 分段 DP，再将它们合并。

DP 状态仅需记录不大于 \(\sqrt{500}\) 的 \(8\) 个质因子的存在状况即可。
稍微修改下定义，定义数集 \(S\) 中的数质因数分解后的小于 \(22\) 的质数组成的集合为 \(\operatorname{P}(S)\)。

设划分后的数列为 \(a\)，当前枚举的数段是第 \(x\) 段，为 \([a_l,a_r]\)，含有的大于 \(22\) 的质因子为 \(y\)。
设 \(g_{x,\operatorname{P}(S1), \operatorname{P}(S2)}\) 表示考虑到前 \(x\) 段数，一方选择的集合 \(S1\) 质因数分解后为 \(\operatorname{P}(S1)\)，另一方为 \(\operatorname{P}(S2)\) 的合法的方案数量。
设 \(f1_{i,\operatorname{P}(S1), \operatorname{P}(S2)}\) 表示由 \(a_1\sim a_i\) 组成的数集 \(S1,S2\) 中，两方分别为 \(\operatorname{P}(S1)\)、\(\operatorname{P}(S2)\)，且含有 \(y\) 的数均属于 \(S1\) 时合法的方案数量。
类似地，设\(f2_{i,\operatorname{P}(S1), \operatorname{P}(S2)}\) 含有 \(y\) 的数均属于 \(S2\) 时合法的方案数量。

初始化，枚举两方所选质数集合 \(S1,S2\)，则有：

\[\begin{aligned} f1_{l-1,S1,S2} = g_{x-1,S1,S2}\\ f2_{l-1,S1,S2} = g_{x-1,S1,S2} \end{aligned}\]

转移时使用刷表法，考虑加入数字 \(a_i\) 的影响，枚举两方所选质数集合 \(S1,S2\)，当 \(S1\cap S2 = \varnothing\) 时，则有：

\[\begin{aligned} f1_{i,S1 | \operatorname{P}(\{a_i\}),S2} = f1_{i,S1 | \operatorname{P}(\{a_i\}),S2} + f1_{i-1,S1,S2}[\operatorname{P}(\{a_i\})\cap S2 = \varnothing]\\ f2_{i,S1,S2 | \operatorname{P}(\{a_i\})} = f2_{i,S1,S2 | \operatorname{P}(\{a_i\})} + f2_{i-1,S1,S2}[\operatorname{P}(\{a_i\})\cap S1 = \varnothing] \end{aligned}\]

分别代表将 \(a_i\) 分入集合 \(S1,S2\) 后的影响，注意后面的条件判断。

得到 \(f\) 后，再将 \(f\) 合并到 \(g\) 中。
枚举两方所选质数集合 \(S1,S2\)，当 \(S1\cap S2 = \varnothing\) 时，则有：

\[g_{x, S1,S2} = f1_{r, S1,S2} + f2_{r, S1, S2} - g_{x-1, S1,S2} \]

会出现两边都不选的情况，且一开始 \(f1,f2\) 都初始化成了 \(g_{x-1\cdots}\)，所以需要减去算重的 \(g_{x-1, S1,S2}\)。

最后的答案即为 \(\sum_{S1\cap S2 = \varnothing} \{g_{x,S1,S2}\}\)。

直接做的空间依旧会爆炸，依旧需要滚动数组优化一下。
对每一个 \(i\) 都做了一遍转移，合并的次数小于 \(n\)，则总时间复杂度为 \(O(n 2^{16})\) 级别。

---

爆零小技巧

注意将数列分段后，转移后要枚举新的数列元素进行转移。

---

代码实现

100pts

//知识点：状压 DP 
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kMaxn = 500 + 10;
const int kAll = 255 + 10;
//=============================================================
int n, mod, p_num;
bool vis[kMaxn];
int a[kMaxn], s[kMaxn], big[kMaxn];  
LL ans, f1[2][kAll][kAll], f2[2][kAll][kAll], g[kAll][kAll];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool ComapreA(int fir_, int sec_) {
  return big[fir_] < big[sec_];
}
void Prepare() { //埃氏筛预处理 
  for (int i = 2; i <= n; ++ i) {
    if (! vis[i]) {
      ++ p_num;
      if (i <= 22) s[i] |= (1 << (p_num - 1));
      Chkmax(big[i], i);
    }
    for (int j = 2; i * j <= n; ++ j) {
      vis[i * j] = true;
      if (! vis[i]) {
        if (i <= 22) s[i * j] |= (1 << (p_num - 1));
        Chkmax(big[i * j], i); //
      }
    }
  }
  //按照所含最大质因子排序 进行分段 
  for (int i = 2; i <= n; ++ i) a[i] = i;
  std::sort(a + 2, a + n + 1, ComapreA);
}
void Dp(int l_, int r_) {
  int now = 1;
  memcpy(f1[0], g, sizeof (f1[0]));
  memcpy(f2[0], g, sizeof (f2[0]));
  for (int i = l_; i <= r_; ++ i, now ^= 1) {
    int x = a[i];
    memcpy(f1[now], f1[now ^ 1], sizeof (f1[now ^ 1]));
    memcpy(f2[now], f2[now ^ 1], sizeof (f2[now ^ 1]));
    
    for (int j = 0; j <= 255; ++ j) {
      for (int k = 0; k <= 255; ++ k) {
        if (j & k) continue ;
        if ((s[x] & j) == 0) {
          f2[now][j][k | s[x]] += f2[now ^ 1][j][k];
          f2[now][j][k | s[x]] %= mod;
        }
        if ((s[x] & k) == 0) {
          f1[now][j | s[x]][k] += f1[now ^ 1][j][k];
          f1[now][j | s[x]][k] %= mod;
        }
      }
    }
  }
  
  for (int j = 0; j <= 255; ++ j) {
    for (int k = 0; k <= 255; ++ k) {
      if (j & k) continue ;
      g[j][k] = f1[now ^ 1][j][k] + f2[now ^ 1][j][k] - g[j][k];
      g[j][k] = (g[j][k] % mod + mod) % mod;
    }
  }
}
//=============================================================
int main() {
  n = read(), mod = read();
  Prepare();
  g[0][0] = 1;
  int l = 2;
  for (int r = 2; r <= n; ++ r) {
    if (big[a[l]] != big[a[r]]) { //
      Dp(l, r - 1);
      l = r;
    }
  }
  Dp(l, n);
  for (int i = 0; i <= 255; ++ i) {
    for (int j = 0; j <= 255; ++ j) {
      if (i & j) continue ;
      ans = (ans + g[i][j]) % mod;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

30pts

//知识点：状压 DP 
/*
By:Luckyblock
Loj 能跑40 /se
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kMaxn = 500 + 10;
const int kMaxAll = 1 << 20;
//=============================================================
int n, mod, ans, p_num;
bool vis[kMaxn];
int all, s[kMaxn], f[2][kMaxAll];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void Prepare() {
  n = read(), mod = read();
  for (int i = 2; i <= n; ++ i) {
    if (! vis[i]) {
      ++ p_num; 
      s[i] |= (1 << (p_num - 1));
    }
    for (int j = 2; i * j <= n; ++ j) {
      vis[i * j] = true;
      if (! vis[i]) {
        s[i * j] |= (1 << (p_num - 1));
      }
    }
  }
}
//=============================================================
int main() {
  Prepare();
  all = (1 << p_num) - 1;
  f[0][0] = 1;
  int now = 1;
  for (int i = 2; i <= n; ++ i, now ^= 1) {
    for (int j = 0; j <= all; ++ j) {
      f[now][j] = f[now ^ 1][j];
    }
    for (int j = 0; j <= all; ++ j) {
      f[now][j | s[i]] += f[now ^ 1][j];
      f[now][j | s[i]] %= mod;
    }
  }
  
  now ^= 1;
  for (int i = 0; i <= all; ++ i) {
    for (int j = 0; j <= all; ++ j) {
      if (i & j) continue ;
      ans += 1ll * f[now][i] * f[now][j] % mod;
      ans %= mod;
    }
  }
  printf("%d\n", ans);
  return 0;
}