问题 A: Six

时间限制: 1 Sec 内存限制: 512 MB

题面

题面谢绝公开。

题解

来写一篇正经的题解。

每一个数对于答案的贡献与数本身无关，只与它包含了哪几个质因数有关。

所以考虑二进制记录状态，记忆化搜索。

可以发现，每个数对于答案的贡献与其数值本身无关，只与其所包含的素数集合有关。

举个例子：$6(2^1*3^1),12(2^2*3^1),24(2^3*3^1)$在二进制下可以压成同一个状态，因为他们都只包含{2,3}这个素数集合。

考虑题意所述：新加入的值满足至多与一个已经加入的值不互质。

换一种理解：新加入的值只要与其中两及以上个值不互质就不是合法状态。

所以考虑对这些素数两两配对，记录数对的出现状态。所以压成$2^{21}$个状态，每个状态代表一个数对。（为什么是$21$？？$21=C_6^2+6$）

没有理解？举个例子：对于样例，$n=6$，有一种不合法的状态为：${2,3,6}$，当我们加入$6$的时候，它本身包含一个数对${2,3}$，而$2$在已选集合中出现过，$3$在已选集合中某个与$2$出现位置不同的位置出现过，则已选集合在数对${2,3}$对应的二进制下为$1$，此时再加入$6$就不合法了。

总的来讲，我们把$n$的每一个约数都视为一个素数集合，如果当前加入的这个元素有两个或两个以上的素数对在已选集合中的两个及以上集合出现过，则状态不合法。

根据这样来压位存储状态，记忆化搜索一发就完了。

具体实现主要难度在预处理？？

代码：

#include<bits/stdc++.h>

#define int long long

#define rint register int

using namespace std;

const int mod=1000000007;

inline void read(int &a)

{

	a=0;int b=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+ch-'0';ch=getchar();}

	a=a*b;return ;

}

int n,sum[1<<6|1],prime[100005],t[7],yxs[100005],cnt[1<<6|1];

int pd[7][7],tag[1<<21|1];

struct node{int x,y;};

bool operator < (node A,node B){

	return (A.x==B.x)?A.y<B.y:A.x<B.x;

}

map <node,int> mp;

inline void devide1()

{

	int lin=n;

	for(rint i=2;i<=sqrt(n);++i)

	{

		if(lin%i==0)

		{

			prime[++prime[0]]=i;

			t[prime[0]]=1<<(prime[0]-1);

			while(lin%i==0)lin/=i;

		}

	}

	if(lin!=1)

	{

		prime[++prime[0]]=lin;

		t[prime[0]]=1<<(prime[0]-1);

	}

	return ;

}

inline void devide2()

{

	for(rint i=1;i<=sqrt(n);++i)

	{

		if(n%i==0)

		{

			if(i!=1)yxs[++yxs[0]]=i;

			if(n/i!=i)yxs[++yxs[0]]=n/i;

		}

	}

	return ;

}

inline void devide3()

{

	for(rint i=1,res;i<=yxs[0];++i)

	{

		res=0;

		for(rint j=1;j<=prime[0];++j)

			if(yxs[i]%prime[j]==0)res|=t[j];

		cnt[res]++;

	}

	return ;

}

inline void start()

{

	devide1();//cout<<1<<endl;

	devide2();//cout<<2<<endl;

	devide3();//cout<<3<<endl;

	pd[1][1]=1<<0,pd[2][2]=1<<1,pd[3][3]=1<<2;

	pd[4][4]=1<<3,pd[5][5]=1<<4,pd[6][6]=1<<5;

	pd[1][2]=pd[2][1]=1<<6;pd[1][3]=pd[3][1]=1<<7;

	pd[1][4]=pd[4][1]=1<<8;pd[1][5]=pd[5][1]=1<<9;

	pd[1][6]=pd[6][1]=1<<10;pd[2][3]=pd[3][2]=1<<11;

	pd[2][4]=pd[4][2]=1<<12;pd[2][5]=pd[5][2]=1<<13;

	pd[2][6]=pd[6][2]=1<<14;pd[3][4]=pd[4][3]=1<<15;

	pd[3][5]=pd[5][3]=1<<16;pd[3][6]=pd[6][3]=1<<17;

	pd[4][5]=pd[5][4]=1<<18;pd[4][6]=pd[6][4]=1<<19;

	pd[5][6]=pd[6][5]=1<<20;

	vector <int> v;

	for(rint i=1;i<=(1<<prime[0])-1;++i)

	{

		v.clear();int res=i;

		for(rint j=1;j<=prime[0];++j)

			if(res&t[j])v.push_back(j);

		for(rint j=0;j<v.size();++j)

			for(rint k=j;k<v.size();++k)

				tag[i]|=pd[v[j]][v[k]];

	}

}

inline int dfs(int us,int ng)

{

	node lode=(node){us,ng};

	if(mp[lode])return mp[lode]%mod;

	for(rint i=1;i<=(1<<prime[0])-1;++i)

	{

		if(tag[i]&ng)continue;

		int lin=ng;

		for(rint j=1;j<=prime[0];++j)

		{

			if(!(i&t[j]))continue;

			for(rint k=1;k<=prime[0];++k)

			{

				if(!(us&t[k]))continue;

				lin|=pd[j][k];

			}

		}

		mp[lode]=(mp[lode]+cnt[i]*(dfs(us|i,lin)%mod+1))%mod;

	}

	return mp[lode]%mod;

}

signed main()

{

	read(n);start();

	printf("%lld\n",dfs(0,0));

	return 0;

}

巴特西

「题解」：$Six$

问题 A: Six

题面

题解

最新文章

热门文章