Submission #14330

#	Time	Username	Problem	Language	Result	Execution time	Memory
14330		ggoh	경비원 (GA8_guard)	C++98	100 / 100	577 ms	1516 KiB

guard

#include<cstdio>
#include<queue>
#include<algorithm>
int D[2][32768],i,j,k,a,t,s,r,u,X=1e9+7,p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
std::vector<int>x[2222];
main()
{
	scanf("%d",&a);
	for(i=0;i<a;i++)
	{
		scanf("%d",&r);
		u=0;
		for(j=0;j<15;j++)
		{
			if(r%p[j]==0)
			{
				u+=(1<<j);
				while(r%p[j]==0)r/=p[j];
			}
		}
		x[r].push_back(u);//r: 1 또는 47 초과 소수 
	}
	
	//47 초과 소수가 없는 수들에 대해서 
	u=0;
	D[0][0]=1;
	for(i=0;i<x[1].size();i++)
	{
		for(j=0;j<32768;j++)
		{
			D[1-u][j]=D[u][j];
			if((j&x[1][i])==x[1][i])D[1-u][j]+=D[u][j-x[1][i]],D[1-u][j]%=X;
		}
		u=1-u;
	}
	
	//47 초과 있는 수에 대해서 
	for(i=49;i<2222;i+=2)
	{
		if(x[i].size())
		{
			for(j=0;j<32768;j++)
			{
				D[1-u][j]=D[u][j];
				for(k=0;k<x[i].size();k++)
				{
					if((j&x[i][k])==x[i][k])
					{
						D[1-u][j]+=D[u][j-x[i][k]];
						D[1-u][j]%=X;
					}
				}
			}
			u=1-u;
		}
	}
	
	s=0;
	for(i=0;i<32768;i++)s+=D[u][i],s%=X;
	printf("%d",(s-a-1+X)%X);
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 27 / 27
• Subtask 5: 36 / 36