Luogu 2150 [NOI 2015] 寿司晚宴

2023-05-16

- - - - 传送门
      - 思路
      - 对于 30%30%30\% 的数据
      - 对于 100%100%100\% 的数据
      - 参考代码

传送门

思路

唉，我太弱了，什么都不会，完全做不来，连暴力都打不来。主要好像是因为我从来没有做过以质因子为状态的状压 DP？唉，我太弱啦！

对于 $30\%$ 的数据

互质的本质是不存在相同的质因子。设 $f_{i, S_1, S_2}$ 表示考虑前 $i$ 个数，第一个人选择的质因子集合为 $s_1$ ，第二个人选择的为 $s_2$ 。状态转移方程为（只能使用刷表法）：

fi+1,S1,S2 += fi,S1,S2 f i + 1 , S 1 , S 2 += f i , S 1 , S 2

$f_{i + 1, S_1, S_2} \text{ += } f_{i, S_1, S_2}$

fi+1,S1∪maski+1,S2 += fi,S1,S2(S2∩maski+1=∅) f i + 1 , S 1 ∪ m a s k i + 1 , S 2 += f i , S 1 , S 2 ( S 2 ∩ m a s k i + 1 = ∅ )

$f_{i + 1, S_1 \cup mask_{i + 1}, S_2} \text{ += } f_{i, S_1, S_2} \pod {S_2 \cap mask_{i + 1} = \emptyset}$

fi+1,S1,S2∪maski+1 += fi,S1,S2(S1∩maski+1=∅) f i + 1 , S 1 , S 2 ∪ m a s k i + 1 += f i , S 1 , S 2 ( S 1 ∩ m a s k i + 1 = ∅ )

$f_{i + 1, S_1, S_2 \cup mask_{i + 1}} \text{ += } f_{i, S_1, S_2} \pod {S_1 \cap mask_{i + 1} = \emptyset}$

时间复杂度为 $O(n \times 2^{20})$ ，显然可以通过，但是需要使用滚动数组。发现其实可以倒序枚举，这样只需要开一维数组就可以了，类似于背包。（神仙们太强啦！一眼就可以一维数组滚动！我看了半天才看出来为什么不会出错（写在代码里的）。唉，我太弱啦！）

对于 $100\%$ 的数据

这种题，一般都会想到 $\sqrt {\;\;}$ 。仔细想一下，发现一个数最多只可能有一个大于 $\sqrt n$ 的质因子（有两个就大于 $n$ 了），所以我们从这里下手。~~然后我就真的不会了。~~

我们把数按照其大于 $\sqrt n$ 的质因子分类，特别地，如果一个数不存在大于 $\sqrt n$ 的质因子，我们令其大质因子为 $1$ 。我们将大质因子相同的数视为同一类，然后一类一类处理。显然，对于两类不同的数，只要满足了小质因子的交集为空集并且对于任意一类数都只有至多一个人去取。特别地，大质因子为 $1$ 的那一类允许两个人同时取。这样，不同类的数就相互独立了。

我们考虑一类一类地进行动态规划。设 $f_{i, j, S_1, S_2}$ 表示考虑了大质因子小于 $i$ 的所有数以及大质因子等于 $i$ 的前 $j$ 个数时，A选的小质因子集合为 $S_1$ ，B 为 $S_2$ 时的方案数（一群神仙，带有滚动数组的状态从来不需要补充完整，直接设，真的是太强啦！我只有把整个状态写出来才看得懂，我真是太弱啦！）。显然对于 $i = 1$ 的情况做法与前面部分相同。

我们考虑 $i > 1$ 的情况。设 $g_{i, j, S_1, S_2, 0 / 1}$ 表示考虑了大质因子小于 $i$ 的所有数以及大质因子等于 $i$ 的前 $j$ 个数，且大质因子等于 $i$ 的数由 A/B 来取（可以选择不取），第一个人选的小质因子集合为 $S_1$ ，第二个人为 $S_2$ 时的方案数。前面已经说了，对于大质因子大于 $1$ 的数最多只能有一个人去取，所以这么设状态是明确的。

显然边界条件为 $g_{i, 0, S_1, S_2, 0 / 1} = f_{i - 1, all, S_1, S_2}$ （都还没有开始选，当然啦）。 $g$ 的转移和之前的 $f$ 很相似，只不过只能有其中一个人进行选择。我们同样使用刷表法：

gi,j+1,S1,S2,0 += gi,j,S1,S2,0 g i , j + 1 , S 1 , S 2 , 0 += g i , j , S 1 , S 2 , 0
$g_{i, j + 1, S_1, S_2, 0} \text{ += } g_{i, j, S_1, S_2, 0}$
gi,j+1,S1∪maski,j+1,S2,0 += gi,j,S1,S2,0(S2∩maski,j+1=∅) g i , j + 1 , S 1 ∪ m a s k i , j + 1 , S 2 , 0 += g i , j , S 1 , S 2 , 0 ( S 2 ∩ m a s k i , j + 1 = ∅ )
$g_{i, j + 1, S_1 \cup mask_{i, j + 1}, S_2, 0} \text{ += } g_{i, j, S_1, S_2, 0} \pod {S_2 \cap mask_{i, j + 1} = \emptyset}$
gi,j+1,S1,S2,1 += gi,j,S1,S2,1 g i , j + 1 , S 1 , S 2 , 1 += g i , j , S 1 , S 2 , 1
$g_{i, j + 1, S_1, S_2, 1} \text{ += } g_{i, j, S_1, S_2, 1}$
gi,j+1,S1,S2∪maski,j+1,1 += gi,j,S1,S2,1(S1∩maski,j+1=∅) g i , j + 1 , S 1 , S 2 ∪ m a s k i , j + 1 , 1 += g i , j , S 1 , S 2 , 1 ( S 1 ∩ m a s k i , j + 1 = ∅ )
$g_{i, j + 1, S_1, S_2 \cup mask_{i, j + 1}, 1} \text{ += } g_{i, j, S_1, S_2, 1} \pod {S_1 \cap mask_{i, j + 1} = \emptyset}$

我们又有：

fi,all,S1,S2=gi,all,S1,S2,0+gi,all,S1,S2,1−fi,0,S1,S2 f i , a l l , S 1 , S 2 = g i , a l l , S 1 , S 2 , 0 + g i , a l l , S 1 , S 2 , 1 − f i , 0 , S 1 , S 2
$f_{i, all, S_1, S_2} = g_{i, all, S_1, S_2, 0} + g_{i, all, S_1, S_2, 1} - f_{i, 0, S_1, S_2}$

两个 $g$ 相加很显然：要么 $A$ 来，要么 $B$ 来，满足加法原理。减去右式的原因是 A 和 B 都可以不选以 $i$ 为大质因子的数，所以这样这种情况就算了两次。显然这种情况的方案数就是 $f_{i, 0, S_1, S_2}$ ，所以减去它就可以了。

然后我们进行滚动数组优化，发现跟前面一样可以不保存 $i$ 和 $j$ ，只需要倒着枚举集合就可以了。这样就有了状态转移方程的形式就和绝大部分题解一样了（唉，神仙的题解我根本看不懂，我太弱啦！）。

参考代码

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <cassert> #include <cctype> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <list> #include <functional> #define loop register int typedef long long LL; typedef unsigned long long ULL; using std::cin; using std::cout; using std::endl; typedef LL INT_PUT; INT_PUT readIn() { INT_PUT a = 0; bool positive = true; char ch = getchar(); while (!(ch == '-' || std::isdigit(ch))) ch = getchar(); if (ch == '-') { positive = false; ch = getchar(); } while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); } return positive ? -a : a; } void printOut(INT_PUT x) { char buffer[20]; int length = 0; if (x < 0) putchar('-'); else x = -x; do buffer[length++] = -(x % 10) + '0'; while (x /= 10); do putchar(buffer[--length]); while (length); } const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; LL mod; int n; #define RunInstance(x) delete new x struct brute { int mask[35]; LL f[1 << 10][1 << 10]; brute() : mask(), f() { for (int i = 2; i <= n; i++) for (int j = 0; j < 10; j++) if (i % prime[j] == 0) mask[i] |= 1 << j; int U = 1 << 10; f[0][0] = 1; for (loop i = 2; i <= n; i++) { loop m = mask[i]; for (loop S1 = U - 1; ~S1; S1--) for (loop S2 = U - 1; ~S2; S2--) if (f[S1][S2]) { if (!(S2 & m)) (f[S1 | m][S2] += f[S1][S2]) %= mod; if (!(S1 & m)) (f[S1][S2 | m] += f[S1][S2]) %= mod; // 唯一会出错的情况是: (!(S2 & mask[i + 1])) && (!(S1 & mask[i + 1])) && ((S1 | mask[i + 1]) == S1)， // 即 f[S1][S2] 在自增后再去更新其它的 // 显然第二个条件和第三个条件矛盾，因此不会出错 } } LL ans = 0; for (loop S1 = 0; S1 < U; S1++) for (loop S2 = 0; S2 < U; S2++) (ans += f[S1][S2]) %= mod; printOut(ans); } }; struct work { struct Number { int num; int mask; int big; Number() {} Number(int num, int mask, int big) : num(num), mask(mask), big(big) {} bool operator<(const Number& b) const { return big < b.big; } }; std::vector<Number> number[505]; LL f[1 << 8][1 << 8]; LL g[2][1 << 8][1 << 8]; work() : f() { for (int i = 2; i <= n; i++) { int t = i; int mask = 0; for (int j = 0; j < 8; j++) { if (t % prime[j]) continue; mask |= 1 << j; while (!(t % prime[j])) t /= prime[j]; } number[t].push_back(Number(i, mask, t)); } int U = 1 << 8; f[0][0] = 1; for (int i = 0; i < number[1].size(); i++) { loop m = number[1][i].mask; for (loop S1 = U - 1; ~S1; S1--) for (loop S2 = U - 1; ~S2; S2--) if (f[S1][S2]) { if (!(S2 & m)) (f[S1 | m][S2] += f[S1][S2]) %= mod; if (!(S1 & m)) (f[S1][S2 | m] += f[S1][S2]) %= mod; } } for (int i = 2; i <= n; i++) if (number[i].size()) { memcpy(g[0], f, sizeof(g[0])); memcpy(g[1], g, sizeof(g[1])); for (int j = 0; j < number[i].size(); j++) { loop m = number[i][j].mask; for (loop S1 = U - 1; ~S1; S1--) for (loop S2 = U - 1; ~S2; S2--) if (g[0][S1][S2]) { if (!(S2 & m)) (g[0][S1 | m][S2] += g[0][S1][S2]) %= mod; if (!(S1 & m)) (g[1][S1][S2 | m] += g[1][S1][S2]) %= mod; } } for (loop S1 = U - 1; ~S1; S1--) for (loop S2 = U - 1; ~S2; S2--) f[S1][S2] = ((g[0][S1][S2] + g[1][S1][S2] - f[S1][S2]) % mod + mod) % mod; } LL ans = 0; for (loop S1 = 0; S1 < U; S1++) for (loop S2 = 0; S2 < U; S2++) (ans += f[S1][S2]) %= mod; printOut(ans); } }; void run() { n = readIn(); mod = readIn(); if (n <= 30) RunInstance(brute); else RunInstance(work); } int main() { run(); return 0; }

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)