Submission #7346

#	Time	Username	Problem	Language	Result	Execution time	Memory
7346		kriii	경비원 (GA8_guard)	C++98	100 / 100	380 ms	1796 KiB

guard

#include <stdio.h>
#include <vector>

const long long mod = 1000000007;
long long ans; int divs[2223],isp[2223],ind[48],cha[2223],p;
std::vector<int> gath[2223],sm;
long long pr[1<<15],nx[1<<15];

int N;

int ch(int x)
{
	int r = 0;
	for (int i=2;i<48;i++) if (!isp[i] && x % i == 0) r |= 1 << ind[i];
	return r;
}

int main()
{
	scanf ("%d",&N);

	for (int i=2;i<=2222;i++) if (!isp[i]){
		for (int j=i;j<=2222;j+=i) divs[j] = i;
		for (int j=i*i;j<=2222;j+=i) isp[j] = 1;
	}
	for (int i=2;i<48;i++) if (!isp[i]){
		ind[i] = p++;
	}
	for (int i=2;i<=2222;i++) cha[i] = ch(i);
	for (int i=0,x;i<N;i++){
		scanf ("%d",&x);
		if (divs[x] >= 48){
			gath[divs[x]].push_back(cha[x/divs[x]]);
		}
		else sm.push_back(cha[x]);
	}

	pr[0] = 1;
	for (int i=48;i<=2222;i++) if (!gath[i].empty()){
		for (int j=0;j<(1<<15);j++) nx[j] = pr[j];
		for (int j=0;j<(1<<15);j++) for (int k=0;k<gath[i].size();k++) if ((j & gath[i][k]) == 0) nx[j|gath[i][k]] += pr[j];
		for (int j=0;j<(1<<15);j++) pr[j] = nx[j] % mod;
	}
	for (int k=0;k<sm.size();k++){
		for (int j=0;j<(1<<15);j++) nx[j] = pr[j];
		for (int j=0;j<(1<<15);j++) if ((j & sm[k]) == 0) nx[j|sm[k]] += pr[j];
		for (int j=0;j<(1<<15);j++) pr[j] = nx[j] % mod;
	}
	for (int i=0;i<(1<<15);i++) ans = (ans + pr[i]) % mod;
	ans = (ans - N - 1 + mod) % mod;
	printf ("%lld\n",ans);

	return 0;
}

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