C. Square Subsets

Codeforces

IDCF895C

Time4000ms

Memory256MB

Difficulty—

bitmaskscombinatoricsdpmath

English · Original

Chinese · Translation

Formal · Original

Petya was late for the lesson too. The teacher gave him an additional task. For some array _a_ Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer. Two ways are considered different if sets of indexes of elements chosen by these ways are different. Since the answer can be very large, you should find the answer modulo 109 + 7. ## Input First line contains one integer _n_ (1 ≤ _n_ ≤ 105) — the number of elements in the array. Second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 70) — the elements of the array. ## Output Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7. [samples] ## Note In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15. In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

Petya 又迟到了课堂。老师给了他一个附加任务：对于某个数组 #cf_span[a]，Petya 需要找出从其中选取非空子集的不同方式的数量，使得这些元素的乘积等于某个整数的平方。如果两种方式所选元素的下标集合不同，则认为这两种方式不同。由于答案可能非常大，你需要求出答案对 #cf_span[109 + 7] 取模的结果。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 数组中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 70]) —— 数组的元素。请输出一个整数 —— 选出若干元素使得其乘积为某个整数的平方的不同方式的数量，结果对 #cf_span[109 + 7] 取模。在第一个样例中，无论以何种方式选择元素，其乘积都是 #cf_span[1]，而 #cf_span[1 = 12]。因此答案是 #cf_span[24 - 1 = 15]。在第二个样例中，有六种不同的方式选择元素使其乘积为 #cf_span[4]，只有一种方式使其乘积为 #cf_span[16]。因此答案是 #cf_span[6 + 1 = 7]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 数组中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 70]) —— 数组的元素。 ## Output 请输出一个整数 —— 选出若干元素使得其乘积为某个整数的平方的不同方式的数量，结果对 #cf_span[109 + 7] 取模。 [samples] ## Note 在第一个样例中，无论以何种方式选择元素，其乘积都是 #cf_span[1]，而 #cf_span[1 = 12]。因此答案是 #cf_span[24 - 1 = 15]。在第二个样例中，有六种不同的方式选择元素使其乘积为 #cf_span[4]，只有一种方式使其乘积为 #cf_span[16]。因此答案是 #cf_span[6 + 1 = 7]。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10^5 $, be the size of the array. Let $ A = (a_1, a_2, \dots, a_n) $, where $ a_i \in \mathbb{Z} $ and $ 1 \leq a_i \leq 70 $, be the input array. Let $ \mathcal{P} = \{ p_1, p_2, \dots, p_m \} $ be the set of prime numbers $ \leq 70 $, so $ m = 19 $. For each $ a_i $, define its **square-free signature** as a vector $ v_i \in \mathbb{F}_2^m $, where the $ j $-th component is the parity (0 or 1) of the exponent of prime $ p_j $ in the prime factorization of $ a_i $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq a_i \leq 70 $ for all $ i \in \{1, \dots, n\} $ **Objective** Count the number of non-empty subsets $ S \subseteq \{1, \dots, n\} $ such that the product $ \prod_{i \in S} a_i $ is a perfect square, modulo $ 10^9 + 7 $. This is equivalent to counting non-empty subsets $ S $ such that $ \sum_{i \in S} v_i = \vec{0} \pmod{2} $, i.e., the sum (XOR) of their signatures is the zero vector in $ \mathbb{F}_2^m $. Let $ V = \{v_1, \dots, v_n\} \subseteq \mathbb{F}_2^m $, and let $ r = \text{rank}(V) $ over $ \mathbb{F}_2 $. Then the number of subsets (including empty) with zero signature is $ 2^{n - r} $. Subtract 1 to exclude the empty subset. **Answer:** $$ \left(2^{n - r} - 1\right) \mod (10^9 + 7) $$

Samples

Input #1

4
1 1 1 1

Output #1

Input #2

4
2 2 2 2

Output #2

Input #3

5
1 2 4 5 8

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Square Subsets",
    "description": {
      "content": "Petya was late for the lesson too. The teacher gave him an additional task. For some array _a_ Petya should find the number of different ways to select non-empty subset of elements from it in such a w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF895C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya was late for the lesson too. The teacher gave him an additional task. For some array _a_ Petya should find the number of different ways to select non-empty subset of elements from it in such a w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 又迟到了课堂。老师给了他一个附加任务：对于某个数组 #cf_span[a]，Petya 需要找出从其中选取非空子集的不同方式的数量，使得这些元素的乘积等于某个整数的平方。\n\n如果两种方式所选元素的下标集合不同，则认为这两种方式不同。\n\n由于答案可能非常大，你需要求出答案对 #cf_span[109 + 7] 取模的结果。\n\n第一行包含一个整数 #cf_span[n] (#cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^5 $, be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z} $ and $ 1 \\leq a_i \\leq 70 $, be the inpu...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments