| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 7346 |
2014-08-02T03:34:50 Z |
kriii |
경비원 (GA8_guard) |
C++ |
|
380 ms |
1796 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 25 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 26 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 27 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 28 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 29 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 31 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 32 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 33 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 34 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 35 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 36 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 37 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 38 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 39 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 40 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 41 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 42 |
Correct |
4 ms |
1796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 23 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 24 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 25 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 28 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 29 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 31 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 32 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 33 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 34 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 35 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 36 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 37 |
Correct |
0 ms |
1796 KB |
Output is correct |
| 38 |
Correct |
8 ms |
1796 KB |
Output is correct |
| 39 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 40 |
Correct |
8 ms |
1796 KB |
Output is correct |
| 41 |
Correct |
8 ms |
1796 KB |
Output is correct |
| 42 |
Correct |
4 ms |
1796 KB |
Output is correct |
| 43 |
Correct |
8 ms |
1796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
1796 KB |
Output is correct |
| 2 |
Correct |
360 ms |
1796 KB |
Output is correct |
| 3 |
Correct |
364 ms |
1796 KB |
Output is correct |
| 4 |
Correct |
364 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
356 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
356 ms |
1796 KB |
Output is correct |
| 7 |
Correct |
364 ms |
1796 KB |
Output is correct |
| 8 |
Correct |
380 ms |
1796 KB |
Output is correct |
| 9 |
Correct |
348 ms |
1796 KB |
Output is correct |
| 10 |
Correct |
344 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
344 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
348 ms |
1796 KB |
Output is correct |
| 13 |
Correct |
340 ms |
1796 KB |
Output is correct |
| 14 |
Correct |
340 ms |
1796 KB |
Output is correct |
| 15 |
Correct |
348 ms |
1796 KB |
Output is correct |
| 16 |
Correct |
360 ms |
1796 KB |
Output is correct |
| 17 |
Correct |
316 ms |
1796 KB |
Output is correct |
| 18 |
Correct |
312 ms |
1796 KB |
Output is correct |
| 19 |
Correct |
312 ms |
1796 KB |
Output is correct |
| 20 |
Correct |
320 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
308 ms |
1796 KB |
Output is correct |
| 22 |
Correct |
308 ms |
1796 KB |
Output is correct |
| 23 |
Correct |
316 ms |
1796 KB |
Output is correct |
| 24 |
Correct |
328 ms |
1796 KB |
Output is correct |
| 25 |
Correct |
268 ms |
1796 KB |
Output is correct |
| 26 |
Correct |
272 ms |
1796 KB |
Output is correct |
| 27 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 28 |
Correct |
272 ms |
1796 KB |
Output is correct |
| 29 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 30 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 31 |
Correct |
268 ms |
1796 KB |
Output is correct |
| 32 |
Correct |
284 ms |
1796 KB |
Output is correct |
| 33 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 34 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 35 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 36 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 37 |
Correct |
204 ms |
1796 KB |
Output is correct |
| 38 |
Correct |
204 ms |
1796 KB |
Output is correct |
| 39 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 40 |
Correct |
220 ms |
1796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
1796 KB |
Output is correct |
| 2 |
Correct |
284 ms |
1796 KB |
Output is correct |
| 3 |
Correct |
260 ms |
1796 KB |
Output is correct |
| 4 |
Correct |
216 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
164 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
164 ms |
1796 KB |
Output is correct |
| 7 |
Correct |
160 ms |
1796 KB |
Output is correct |
| 8 |
Correct |
164 ms |
1796 KB |
Output is correct |
| 9 |
Correct |
160 ms |
1796 KB |
Output is correct |
| 10 |
Correct |
164 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
160 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
96 ms |
1796 KB |
Output is correct |
| 13 |
Correct |
104 ms |
1796 KB |
Output is correct |
| 14 |
Correct |
100 ms |
1796 KB |
Output is correct |
| 15 |
Correct |
100 ms |
1796 KB |
Output is correct |
| 16 |
Correct |
100 ms |
1796 KB |
Output is correct |
| 17 |
Correct |
100 ms |
1796 KB |
Output is correct |
| 18 |
Correct |
96 ms |
1796 KB |
Output is correct |
| 19 |
Correct |
24 ms |
1796 KB |
Output is correct |
| 20 |
Correct |
24 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
28 ms |
1796 KB |
Output is correct |
| 22 |
Correct |
24 ms |
1796 KB |
Output is correct |
| 23 |
Correct |
24 ms |
1796 KB |
Output is correct |
| 24 |
Correct |
20 ms |
1796 KB |
Output is correct |
| 25 |
Correct |
24 ms |
1796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
1796 KB |
Output is correct |
| 2 |
Correct |
272 ms |
1796 KB |
Output is correct |
| 3 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 4 |
Correct |
344 ms |
1796 KB |
Output is correct |
| 5 |
Correct |
280 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
324 ms |
1796 KB |
Output is correct |
| 7 |
Correct |
184 ms |
1796 KB |
Output is correct |
| 8 |
Correct |
312 ms |
1796 KB |
Output is correct |
| 9 |
Correct |
348 ms |
1796 KB |
Output is correct |
| 10 |
Correct |
372 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
268 ms |
1796 KB |
Output is correct |
| 13 |
Correct |
256 ms |
1796 KB |
Output is correct |
| 14 |
Correct |
328 ms |
1796 KB |
Output is correct |
| 15 |
Correct |
272 ms |
1796 KB |
Output is correct |
| 16 |
Correct |
316 ms |
1796 KB |
Output is correct |
| 17 |
Correct |
172 ms |
1796 KB |
Output is correct |
| 18 |
Correct |
300 ms |
1796 KB |
Output is correct |
| 19 |
Correct |
332 ms |
1796 KB |
Output is correct |
| 20 |
Correct |
352 ms |
1796 KB |
Output is correct |
| 21 |
Correct |
244 ms |
1796 KB |
Output is correct |
| 22 |
Correct |
240 ms |
1796 KB |
Output is correct |
| 23 |
Correct |
232 ms |
1796 KB |
Output is correct |
| 24 |
Correct |
300 ms |
1796 KB |
Output is correct |
| 25 |
Correct |
248 ms |
1796 KB |
Output is correct |
| 26 |
Correct |
280 ms |
1796 KB |
Output is correct |
| 27 |
Correct |
152 ms |
1796 KB |
Output is correct |
| 28 |
Correct |
272 ms |
1796 KB |
Output is correct |
| 29 |
Correct |
300 ms |
1796 KB |
Output is correct |
| 30 |
Correct |
320 ms |
1796 KB |
Output is correct |
| 31 |
Correct |
216 ms |
1796 KB |
Output is correct |
| 32 |
Correct |
208 ms |
1796 KB |
Output is correct |
| 33 |
Correct |
200 ms |
1796 KB |
Output is correct |
| 34 |
Correct |
256 ms |
1796 KB |
Output is correct |
| 35 |
Correct |
212 ms |
1796 KB |
Output is correct |
| 36 |
Correct |
244 ms |
1796 KB |
Output is correct |
| 37 |
Correct |
128 ms |
1796 KB |
Output is correct |
| 38 |
Correct |
236 ms |
1796 KB |
Output is correct |
| 39 |
Correct |
264 ms |
1796 KB |
Output is correct |
| 40 |
Correct |
272 ms |
1796 KB |
Output is correct |
