NOI 2015 寿司晚宴

发表于 | 更新于

Link

这个做法非常喵啊

Solution

也就是说两个集合里不能有相同的质因子 那就质因子分解，状压，似乎可以处理30以内的，总共10个质数的情况 可以发现，状压的很多维是没用的。具体说，对于每个质因子，只会出现[np][\dfrac np]次。pp越大，越浪费。 此时可以想到O(n)O(\sqrt n)分解质因数的做法：用n\sqrt n以内的数字试除，最后判断是否为1。也就是说，每个数字都至多只有一个≥n\ge \sqrt n的质因子。而在n\sqrt n范围内只有88个质数，那就利用这个性质搞一些事情吧。 好了。每个数字分解，记录≤n\le \sqrt n的八个质数的状态，再记录剩下的唯一一个大质数。 然后把大质数相同的一起DP。 f[S1][S2]f[S_1][S_2]表示相应状态的方案数目，g[0/1][S1][S2]g[0/1][S_1][S_2]表示这个大质数给了0/10/1(给了不一定要了)的方案数目。g[0/1]g[0/1]的转移是互相独立的。当处理完一组大质数相同的数的时候，((f[S1][S2])∗=−1)+=(g[0][S1][S2]+g[1][S1][S2])((f[S_1][S_2])*=-1)+=(g[0][S_1][S_2]+g[1][S_1][S_2])

枚举SubSet

我不停地问自己：一定要写的这么诡异吗 

1
#define subset(x,ALL) for(int __S__=(ALL),x=__S__,__flag__=0;!__flag__;x=(x-1)&__S__,__flag__=(x==__S__))

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define subset(x,ALL) for(int __S__=(ALL),x=__S__,__flag__=0;!__flag__;x=(x-1)&__S__,__flag__=(x==__S__))
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::sort;
const int MAXN=500+11,pc=8,prime[]={2,3,5,7,11,13,17,19},S=(1<<8)-1,MAXS=S+11;
int P;
struct Number
{
	int bigprime;
	int other;
	Number(){}
	Number(int x)
	{
		for(int i=0;i<pc && x>=prime[i];++i)
			if(x%prime[i]==0)
			{
				other|=(1<<i);
				do x/=prime[i];
				while(x%prime[i]==0);
			}
		bigprime=x;
	}
	bool operator <(const Number& a)const
	{
		if(bigprime!=a.bigprime)return bigprime<a.bigprime;
		return other<a.other;
	}
}num[MAXN];
int Solve(int n)
{
	static ll f[MAXS][MAXS],g[2][MAXS][MAXS];
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	for(int i=1;i<=n;++i)
		new(num+i) Number(i);
	sort(num+2,num+1+n);
	f[0][0]=g[0][0][0]=g[1][0][0]=1;
	for(int i=2;i<=n+1;++i)
	{
		if(num[i-1].bigprime==1 || num[i].bigprime!=num[i-1].bigprime)
		{
			for(int s1=0;s1<=S;++s1)
				subset(s2,S&(~s1))
				{
					((f[s1][s2]*=-1)+=(g[0][s1][s2]+g[1][s1][s2]))%=P;
					g[0][s1][s2]=g[1][s1][s2]=f[s1][s2];
				}	
		}
		if(i==n+1) break;
		int cur=num[i].other;
		for(int s1=S;~s1;--s1)
			subset(s2,S&(~s1))
			{
				((g[0][s1|cur][s2])+=g[0][s1][s2])%=P;
				((g[1][s1][s2|cur])+=g[1][s1][s2])%=P;
			}
	}
	ll Ans=0;
	for(int s1=0;s1<=S;++s1)
		subset(s2,S&(~s1))
			(Ans+=f[s1][s2])%=P;
	(Ans+=P)%=P;
	return Ans;
}
int main()
{
	freopen("input","r",stdin);
	int n;get(n),get(P);
	put(Solve(n)),putchar('\n');
	return 0;
}