「NOI2018模拟1」测试test - 状压动规

题目大意

    在你的帮助下，Winedag 愉快地在 deadline 前造完了他的题目。
    虽然 Winedag 非常牛逼，但 Wetmath 还是要求他参加模拟考试。
    Winedag 要考的题目一共有$n$道，对于第$i$道题，如果AC了，那么得分为$i$，否则得分为$1$，这套题的得分为所有题的得分的积，如果没有AC任何题，那么得分为$1$。
    就在Winedag准备切题如麻的时候，突然想起了一个事情，之前有人告诉他：在评测结束以后，会有一个小斗士来把所有分数不为完全平方数的人的程序删掉，分数变为$0$分。
    Winedag 想知道他有多少种方案能得到他能得到的最高分，但是他忙于写代码，所以他只能来找你帮忙。

---

题目分析

简单的状压动规。
将$n!$质因数分解，对于次数为奇数的质因子，必须去掉且只能去掉一个才能构成最大的完全平方数。
因此将所有次数为奇数的质因子（根号以内的最多$16$个）单独提出做状压。
对于每个不含平方因子的数，计算其分解后压缩的状态。
用vector[x]保存最大质因数为$x$的所有状态（若最大质因数在根号范围内，则$x=0$）。

对于$x=0$的状态，做一个状压的背包即可解决。
对于其余的$x$，只能选一个且必须选一个在$x$中的合法状态，同样做一次背包解决。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=3005,maxs=1<<17;

int n,cnt=0,p[maxn],u[maxn];
LL f[maxs],g[maxs];
bool vst[maxn],sig[maxn];

void Mobius_Table(int n) {
	u[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i])p[++cnt]=i,u[i]=-1;
		for(int j=1; j<=cnt&&p[j]*i<=n; j++) {
			vst[p[j]*i]=1;
			if(i%p[j]==0) {u[p[j]*i]=0;break;}
			u[p[j]*i]=-u[i];
		}
	}
}

int Cal(int x,int k) {
	int ans=0;
	while(x) {ans+=x/k;x/=k;}
	return ans;
}

vector<int> a,vec[maxn];

int main() {
	n=Get_Int();
	Mobius_Table(n);
	for(int i=1; i<=cnt; i++)if(Cal(n,p[i])&1)a.push_back(p[i]),sig[i]=1;
	int t=ceil(sqrt(n)),Max=0;
	for(int i=2; i<=n; i++)
		if(u[i]) {
			bool bj=1;
			for(int j=1; j<=cnt; j++)if(i%p[j]==0)bj&=sig[j];
			if(!bj)continue;
			int up=0,S=0;
			for(int j=0; j<a.size(); j++)
				if(i%a[j]==0) {
					if(a[j]>=t)up=a[j];
					else S|=1<<j,Max=max(Max,j+1);
				}
			vec[up].push_back(S);
		}
	Max=1<<Max;
	f[0]=1;
	for(auto T:vec[0])
		for(int S=Max-1; S>=0; S--)
			if((S&T)==T)f[S]+=f[S^T];
	for(int i=1; i<=n; i++) { //只选一个
		if(vec[i].empty())continue;
		fill(g,g+Max,0);
		for(auto T:vec[i])
			for(int S=0; S<Max; S++)
				if((S&T)==T)g[S]+=f[S^T];
		copy(g,g+Max,f);
	}
	printf("%lld\n",f[Max-1]<<1);
	return 0;
}