[CF895C]Square Subsets

题目大意：给一个集合$S$（$1\leq S_i\leq 70$），选择一个非空子集，使它们的乘积等于某个整数的平方的方法的数量。求方案数，若两种方法选择的元素的索引不同，则认为是不同的方法。

题解：$70$以内的质数只有$19$个，考虑状压$DP$，$f_{i,j}$表示这个数为$i$，若$j$二进制下的第$k$位为$1$，表示它含第$k$个质数奇数个，转移显然

卡点：无

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 500010

using namespace std;

const int mod = 1000000007;

const int plist[19] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};

int n, a;

int cnt[71], now = 1, past;

long long f[2][1 << 19];

long long pw(long long base, long long p) {

	if (p < 1) return 1;

	long long ans = 1;

	for (; p; p >>= 1, base = base * base % mod)

		if (p & 1) ans = ans * base % mod;

	return ans;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%d", &a);

		cnt[a]++;

	}

	f[now][0] = 1;

	for (int i = 1; i <= 70; i++) {

		now ^= past ^= now ^= past;

		if (cnt[i]) {

			memset(f[now], 0, sizeof f[now]);

			int cur = 0, Yx = i;

			for (int j = 0; j < 19; j++) {

				while (Yx % plist[j] == 0) {

					Yx /= plist[j];

					cur ^= 1 << j;

				}

			}

			long long tmp = pw(2, cnt[i] - 1);

			for (int j = 0; j < 1 << 19; j++) {

				f[now][j] = (f[now][j] + f[past][j] * tmp) % mod;

				f[now][j ^ cur] = (f[now][j ^ cur] + f[past][j] * tmp) % mod;

			}

		} else now ^= past ^= now ^= past;

	}

	printf("%lld\n", (f[now][0] - 1 + mod) % mod);

	return 0;

}

巴特西

[CF895C]Square Subsets

最新文章

热门文章