luogu P2150 [NOI2015] 寿司晚宴

题面传送门
首先考虑一个dp：设\(f_{i,S1,S2}\)为到了第\(i\)个数，两个集合分别为\(S1,S2\)的方案数，其中要求\(S1\&S2=\empty\)
但是小于\(500\)的质数很多，不可能都状压起来。
考虑每个数的性质：大于\(\sqrt n\)的因子最多只有一个。
所以可以将这个质因子单独拿出来，并且dp的时候将这个最大质因子相同的放在一起dp，强制规定不能同时放在\(S1\)或同时放在\(S2\)
然后状压就只有\(8\)个质因子了，时间复杂度\(O(n2^{16})\)，实现精细能做到\(O(n3^8)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (1000+5)
#define M (1<<8)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,p,x,y,Ne,La,cnt;ll dp[2][M+5][M+5],G[M+5][M+5],Ans;int pr[9]={2,3,5,7,11,13,17,19};vector S[N];
int main(){
//	freopen("1.in","r",stdin);
	RI i,j,h;scanf("%d%d",&n,&p);cnt=n;for(i=2;i<=n;i++) {
		y=0;x=i;for(j=0;j<8;j++){if(x%pr[j]) continue;
			y|=(1<