C++14(g++5.4) 解法, 执行用时: 72ms, 内存消耗: 592K, 提交时间: 2019-06-21 22:31:06

#include <bits/stdc++.h>
using namespace std;

const int P = 1000000007;
int n, m, f[1 << 11], g[1 << 11], p[1005], tot;
bool np[1005];
vector<int> gr[2005];

pair<int, int> divide(int x) {
	int tmp = x, s = 0;
	for (int i = 0; i < tot; ++i)
		if (x % p[i] == 0) {
			s |= 1 << i;
			while (x % p[i] == 0) x /= p[i];
		}
	return make_pair(s, x == 1 ? 1000 + tmp : x);
}
void add(const vector<int> &v) {
	for (int i = 0; i < 1 << tot; ++i)
		if (f[i]) {
			g[i] = (g[i] + f[i]) % P;
			for (int s : v)
				if ((s & i) == 0)
					g[i | s] = (g[i | s] + f[i]) % P;
		}
	copy(g, g + (1 << tot), f);
	fill(g, g + (1 << tot), 0);
}
void del(const vector<int> &v) {
	bool flag = count(v.begin(), v.end(), 0);
	for (int i = 0; i < 1 << tot; ++i) {
		g[i] = f[i];
		for (int s : v)
			if (s && (s & i) == s)
				g[i] = (g[i] - g[i - s]) % P;
		if (flag)
			g[i] = (P + 1LL) / 2 * g[i] % P;
	}
	copy(g, g + (1 << tot), f);
	fill(g, g + (1 << tot), 0);
}
void add(const pair<int, int> &p) {
	del(gr[p.second]);
	gr[p.second].push_back(p.first);
	add(gr[p.second]);
}
void del(const pair<int, int> &p) {
	del(gr[p.second]);
	vector<int> tmp;
	bool first = true;
	for (int x : gr[p.second]) {
		if (x != p.first) tmp.push_back(x);
		else if (first) first = false;
		else tmp.push_back(x);
	}
	gr[p.second] = tmp;
	add(gr[p.second]);
}

int main() {
	for (int i = 2; i * i <= 1000; ++i) {
		if (!np[i]) p[tot++] = i;
		for (int j = 0; j < tot && p[j] * i <= 1000; ++j) {
			np[p[j] * i] = true;
			if (i % p[j] == 0) break;
		}
	}
	f[0] = 1;
	scanf("%d", &n);
	for (int i = 1, x; i <= n; ++i)
		scanf("%d", &x), add(divide(x));
	scanf("%d", &m);
	for (int op, x; m--;) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d", &x), add(divide(x));
		}
		if (op == 2) {
			scanf("%d", &x), del(divide(x));
		}
		if (op == 3) {
			int ans = 0;
			for (int i = 0; i < 1 << tot; ++i)
				ans = (ans + f[i]) % P;
			printf("%d\n", (ans + P) % P);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 632K, 提交时间: 2019-06-22 08:15:22

#include<bits/stdc++.h>

using namespace std;

const int N = 1234, mod = 1e9 + 7, prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

void add(int& x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

void sub(int& x, int y) {
  x -= y;
  if (x < 0) {
    x += mod;
  }
}

int n, m, dp[1 << 11];
multiset<int> sets[N];

pair<int, int> divide(int x) {
  int y = x, s = 0;
  for (int i = 0; i < 11; ++i) {
    if (y % prime[i] == 0) {
      s |= 1 << i;
      while (y % prime[i] == 0) {
        y /= prime[i];
      }
    }
  }
  return make_pair(y == 1 ? x : y, s);
}

void add(multiset<int> sets) {
  for (int i = (1 << 11) - 1; ~i; --i) {
    bool zero = false;
    for (auto s : sets) {
      if (s && !(s & i)) {
        add(dp[s | i], dp[i]);
      }
      if (!s) {
        zero = true;
      }
    }
    if (zero) {
      dp[i] = (dp[i] << 1) % mod;
    }
  }
}

void sub(multiset<int> sets) {
  for (int i = 0; i < 1 << 11; ++i) {
    for (auto s : sets) {
      if (s && !(s & i)) {
        sub(dp[s | i], dp[i]);
      }
      if (!s) {
        dp[i] = (long long) dp[i] * (mod + 1 >> 1) % mod;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  dp[0] = 1;
  for (int i = 1, x; i <= n; ++i) {
    cin >> x;
    pair<int, int> foo = divide(x);
    sub(sets[foo.first]);
    sets[foo.first].insert(foo.second);
    add(sets[foo.first]);
  }
  cin >> m;
  while (m--) {
    int op, x;
    cin >> op;
    if (op == 1 || op == 2) {
      cin >> x;
      pair<int, int> foo = divide(x);
      sub(sets[foo.first]);
      if (op == 1) {
        sets[foo.first].insert(foo.second);
      } else {
        sets[foo.first].erase(sets[foo.first].find(foo.second));
      }
      add(sets[foo.first]);
    } else {
      int answer = 0;
      for (int i = 0; i < 1 << 11; ++i) {
        add(answer, dp[i]);
      }
      cout << answer << '\n';
    }
  }
  return 0;
}