Uoj 129 寿司晚宴

显然合法性只与每个数所含的质因子有关,考虑状压 \(dp\) 若记录所有质因子状态显然爆炸,注意到每个数最多有一个超过 \(\sqrt 500\) 的大质因子,而其他的小质因子只有 \(8\) 种.所以可以对小质因子状压,大质因子单独考虑.
记 \(f[j][k]\) 表示当前第一个人选择的数含有质因子的集合为 \(j\) ,第二个人的为 \(k\) 时的方案数.
\(g[0/1][j][k]\) 表示当前第一个人选择的数含有质因子的集合为 \(j\) ,第二个人的为 \(k\) ,把这个大质因子放入第一个/第二个人中的方案数.
计算时,若新加入的大质数与上一个不同,就将 \(f\) 赋值到 \(g\) 中.
然后\(dp\) 计算 \(g\) .
若新加入的大质数与下一个不同,就根据 \(g\) 计算 \(f\) ,计算时要减去一次两个都不放的情况.
时间复杂度为 \(O(8^8)\),在 \(1e7\) 的级别,因为很多状态不合法,不会有取模运算,常数较小,可以通过.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

	int out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		fh=-1,jp=getchar();

	while (jp>='0'&&jp<='9')

		out=out*10+jp-'0',jp=getchar();

	return out*fh;

}

const int MAXP=8,MAXS=(1<<8)+10,MAXN=520;

const int lim=1<<8;

int prime[]= {2,3,5,7,11,13,17,19};

int f[MAXS][MAXS],g[2][MAXS][MAXS];

int n,P;

inline int add(int a,int b)

{

	return (a + b) % P;

}

inline int mul(int a,int b)

{

	return 1LL * a * b % P;

}

void upd(int &x,int y)

{

	x=add(x,y);

}

struct node

{

	int s;

	int bp;//大质因子

	bool operator < (const node &rhs) const

	{

		return bp<rhs.bp;

	}

} a[MAXN];

void init(int i)

{

	int x=i;

	int s=0;

	for(int j=0; j<MAXP; ++j)

		{

			if(x%prime[j]==0)

				{

					s|=1<<j;

					while(x%prime[j]==0)

						x/=prime[j];

				}

		}

	a[i].s=s;

	a[i].bp=x;

}

int main()

{

	n=read(),P=read();

	for(int i=2; i<=n; ++i)

		init(i);

	f[0][0]=1;

	int ans=0;

	sort(a+2,a+2+n-1);

	for(int i=2; i<=n; ++i)

		{

			if(i==2 || a[i].bp==1 || a[i].bp!=a[i-1].bp)

				{

					memcpy(g[0],f,sizeof f);

					memcpy(g[1],f,sizeof f);

				}

			for(int j=lim-1; j>=0; --j)

				for(int k=lim-1; k>=0; --k)

					{

						if(j&k)

							continue;

						if(!(a[i].s & k))

							upd(g[0][j|a[i].s][k],g[0][j][k]);

						if(!(a[i].s & j))

							upd(g[1][j][k|a[i].s],g[1][j][k]);

					}

			if(i==n || a[i].bp==1 || a[i].bp!=a[i+1].bp)

				{

					for(int j=lim-1; j>=0; --j)

						for(int k=lim-1; k>=0; --k)

							{

								if(j&k)

									continue;

								f[j][k]=add(add(g[0][j][k],g[1][j][k]),P-f[j][k]);

								if(i==n)

									upd(ans,f[j][k]);

							}

				}

		}

	cout<<ans<<endl;

	return 0;

}

巴特西

Uoj 129 寿司晚宴

Uoj 129 寿司晚宴

最新文章

热门文章