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\) 和 \(f2\) 都可以不取这一段的数，那么 \(dp_{S_1,S_2}\) 就被算了两次，减掉即可。
时间复杂度为 \(O(n2^{16})\)。
完整代码：
#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 感谢分享，学习下。 感谢发布原创作品，程序园因你更精彩 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了 谢谢楼主提供！ 谢谢楼主提供！ 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 谢谢分享，辛苦了 热心回复！ 感谢，下载保存了 鼓励转贴优秀软件安全工具和文档！ 感谢，下载保存了 yyds。多谢分享 谢谢分享，辛苦了 分享、互助 让互联网精神温暖你我 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，下载保存了，貌似很强大 这个好，看起来很实用
页:
[1]
2