ToB企服应用市场:ToB评测及商务社交产业平台

标题: P2150 [NOI2015] 寿司晚宴 [打印本页]

作者: 伤心客 时间: 2024-8-5 20:50
标题: P2150 [NOI2015] 寿司晚宴
思路：

留意到对于每个数，其 \(>19\) 的质因数最多只有 \(1\) 个，称为大质数；对于 \(\le 19\) 的质因数有 \(8\) 个，称为小质数。
设第 \(i\) 个数的小质数集合为 \(h_i\)。
那么考虑对于所有数按照大质数从小到大排序，那么对于大质数类似的一段，只能放在两个集合中的一个。
考虑状态压缩 \(dp\)，定义 \(dp_{S_1,S_2}\) 表示对于取完 \(i\)（可以滚动数组）个数后第一/二个集合的小质数集合，\(f1_{S_1,S_2}\) 表示这一段的数都放在第一个集合的方案数，\(f2_{S_1,S_2}\) 表示这一段的数都放在第二个集合的方案数。
则状态转移方程为（起首要满足 \(S_1\) 与 \(S_2\) 没有交集，即 \(S_1 \operatorname{and} S_2 = 0\)）：

\[f1_{S_1 \operatorname{or} data_i,S_2} += f1_{S_1,S_2} [S_2 \operatorname{and} h_i = 0]\]

\[f2_{S_1,S_2 \operatorname{or} data_i} += f1_{S_1,S_2} [S_1 \operatorname{and} h_i = 0]\]

\[dp_{S_1,S_2} = f1_{S_1,S_2} + f2_{S_1,S_2} - dp_{S_1,S_2}\]
因为 \(f1\) 和 \(f2\) 都可以不取这一段的数，那么 \(dp_{S_1,S_2}\) 就被算了两次，减掉即可。
时间复杂度为 \(O(n2^{16})\)。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=505,M=8,S=(1ll

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)