Submission #7913

#	Time	Username	Problem	Language	Result	Execution time	Memory
7913		gs13068	경비원 (GA8_guard)	C++98	100 / 100	512 ms	1516 KiB

guard

#include<cstdio>
#include<vector>
#include<algorithm>

#define MOD 1000000007

std::vector<int> a[2222];

int p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int d[2][32768];

int main()
{
	int *now,*next,*temp;
	int i,j,k,n,t;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		k=0;
		for(j=0;j<15;j++)if(t%p[j]==0)
		{
            k|=1<<j;
            while(t%p[j]==0)t/=p[j];
		}
        a[t].push_back(k);
	}
	now=d[0];
	next=d[1];
    now[0]=1;
    for(i=0;i<a[1].size();i++)
	{
        for(j=0;j<32768;j++)
		{
			next[j]=now[j];
			if((j&a[1][i])==a[1][i])(next[j]+=now[j&~a[1][i]])%=MOD;
		}
		temp=now;
		now=next;
		next=temp;
	}
	for(i=2;i<2222;i++)if(a[i].size())
	{
        for(j=0;j<32768;j++)
		{
			next[j]=now[j];
			for(k=0;k<a[i].size();k++)if((j&a[i][k])==a[i][k])(next[j]+=now[j&~a[i][k]])%=MOD;
		}
		temp=now;
		now=next;
		next=temp;
	}
	i=0;
	for(j=0;j<32768;j++)(i+=now[j])%=MOD;
	printf("%d",i-n-1);
}

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