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})\)

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#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<<M);
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll x;
	ll data;
	bool operator<(const Node&rhs)const{
		return x<rhs.x;
	}
}a[N];
ll n,x,ans,mod;
ll dp[S][S],f1[S][S],f2[S][S];
ll P[]={2,3,5,7,11,13,17,19};
bool End;
int main(){
	n=read(),mod=read();
	for(int i=2;i<=n;i++){
		x=i;
		for(int j=0;j<8;j++){
			if(x%P[j]==0){
				a[i].data|=(1ll<<j);
				while(x%P[j]==0)
				  x/=P[j];
			}
		}
		if(x!=1)
		  a[i].x=x;
	}
	dp[0][0]=1;
	sort(a+2,a+n+1);
	for(int i=2;i<=n;i++){
		if(!a[i].x||a[i].x!=a[i-1].x){
			for(int X=0;X<S;X++)
			  for(int Y=0;Y<S;Y++)
			    f1[X][Y]=f2[X][Y]=dp[X][Y];
		}
		for(int X=S-1;X>=0;X--){
			for(int Y=S-1;Y>=0;Y--){
				if(X&Y)
				  continue;
				if((a[i].data&Y)==0)
				  f1[X|a[i].data][Y]=Add(f1[X|a[i].data][Y],f1[X][Y]);
				if((a[i].data&X)==0)
				  f2[X][Y|a[i].data]=Add(f2[X][Y|a[i].data],f2[X][Y]);
			}
		}
		if(i==n||a[i].x!=a[i+1].x||!a[i].x){
			for(int X=0;X<S;X++)
			  for(int Y=0;Y<S;Y++)
			    dp[X][Y]=(f1[X][Y]+f2[X][Y]-dp[X][Y]+mod)%mod;			
		}
	}
	for(int X=0;X<S;X++)
	  for(int Y=0;Y<S;Y++)
		ans=Add(ans,dp[X][Y]);
	write(ans);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

热门相关:傅爷怀里的假千金真绝了   贩罪   拳皇之梦   误踩老公底线:甜心难招架!   福晋有喜:四爷,宠上天!