Submission #7851

#	Time	Username	Problem	Language	Result	Execution time	Memory
7851		ainu7	경비원 (GA8_guard)	C++98	100 / 100	272 ms	1864 KiB

guard

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mmod = 1000000007;
const int max_n = 2222;

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

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

  vector<int> mask[max_n+1];

  for (int i=0; i<n; i++) {
    int temp;
    scanf("%d", &temp);
    int bit = 0;
    for (int j=0; j<small_cnt; j++) {
      int occ = 0;
      while (temp % small_prime[j] == 0) {
        occ = 1;
        temp /= small_prime[j];
      }
      if (occ) bit |= 1 << j;
    }
    for (int j=50; j<=max_n; j++)
      if (j * j == temp) temp = j;
    mask[temp].push_back(bit);
  }

  int prv[1<<small_cnt] = {0};
  prv[0] = 1;

  // stage 1. mask[1]
  for (int i=0; i<mask[1].size(); i++) {
    int bit = mask[1][i];
    for (int j=(1<<small_cnt)-1; j>=0; j--) {
      if ((j&bit) == bit) {
        prv[j] = prv[j] + prv[j-bit];
        if (prv[j] >= mmod) prv[j] -= mmod;
      }
    }
  }
  
  // stage 2. mask[50++]
  for (int i=50; i<=max_n; i++) {
    if (!mask[i].size()) continue;

    // select 0 or 1 of them.
    int nxt[1<<small_cnt];
    for (int j=0; j<(1<<small_cnt); j++) nxt[j] = prv[j];
    for (int j=0; j<mask[i].size(); j++) {
      int bit = mask[i][j];
      for (int k=0; k<(1<<small_cnt); k++)
        if ((k&bit) == bit) {
          nxt[k] = nxt[k] + prv[k-bit];
          if (nxt[k] >= mmod) nxt[k] -= mmod;
        }
    }

    for (int j=0; j<(1<<small_cnt); j++) prv[j] = nxt[j];
  }

  int res = mmod - n - 1;
  for (int i=0; i<(1<<small_cnt); i++)
    res = (res + prv[i]) % mmod;
  printf("%d\n", res);
}

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