字数

391 字

阅读时间

2 分钟

来源：Zhu and 772002

题意

给长度为 $n(1\le n\le 300)$ 的数组 $a(1\le a_i\le {10}^{18})$

每个数拥有的指数因子大小不超过 $2000$

选择k个数，要求相乘的数是完全平方数

问有多少选择方式，只要位置不同就算方式不同

思路

完全平方数，要求质因数是偶数，即选择的所有数分解成质因数后，在2,3,5这些数上的的数量是偶数

0表示偶数，1表示奇数个质因数
	2 3 5 7
6   1 1 0 0
21  0 1 0 1
30  1 1 1 0
70  1 0 1 1

以上，以2为例写出式子 $(1\ast x_1+0\ast x_2+1\ast x_3+1\ast x_4)\mathrm{\%}2=0$ ，那么解出合适的 $x$ ，就可以确定方案数

$\mathrm{\%}2$ 操作转化为异或：$x_1⨁x_3⨁x_4=0$

到最后会出现若干自由元

将异或式子转化为：
	2 3 5 7
6   1 1 0 0
21  0 1 0 1
30  1 1 1 0
70  1 0 1 1
=>
	2 3 5 7
6   1 0 0 0
21  0 1 0 1
30  0 0 1 0
70  0 0 0 0

如上式，$x_3$ 状态可以确定，但是 $x_2$ 的状态随自由元 $x_4$ 变化

一旦确定了所有自由元的取与不取就能获得一个解，那么 $n$ 个自由元就是 $2^n$ 个解

但是至少要选取一个数，所以排除所有自由元都不选择的唯一一种状态，答案就是 $2^n-1$

代码

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

65bbf-update 算法学习 and modify 算法题解

3f371-update 算法题解

f1a81-update 过去的笔记（在博客园发布的）