{"problem":{"name":"D. Perfect Groups","description":{"content":"SaMer has written the greatest test case of all time for one of his problems. For a given array of integers, the problem asks to find the minimum number of groups the array can be divided into, such t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF980D"},"statements":[{"statement_type":"Markdown","content":"SaMer has written the greatest test case of all time for one of his problems. For a given array of integers, the problem asks to find the minimum number of groups the array can be divided into, such that the product of any pair of integers in the same group is a perfect square.\n\nEach integer must be in exactly one group. However, integers in a group do not necessarily have to be contiguous in the array.\n\nSaMer wishes to create more cases from the test case he already has. His test case has an array $A$ of $n$ integers, and he needs to find the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$ for each integer $k$ between $1$ and $n$ (inclusive).\n\n## Input\n\nThe first line of input contains a single integer $n$ ($1 \\leq n \\leq 5000$), the size of the array.\n\nThe second line contains $n$ integers $a_1$,$a_2$,$\\dots$,$a_n$ ($-10^8 \\leq a_i \\leq 10^8$), the values of the array.\n\n## Output\n\nOutput $n$ space-separated integers, the $k$\\-th integer should be the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"SaMer 为他的一道题编写了有史以来最伟大的测试用例。对于一个整数数组，该题要求找出将数组划分为最少的组数，使得同一组中任意两个整数的乘积都是完全平方数。\n\n每个整数必须恰好属于一个组。然而，同一组中的整数在数组中不必连续。\n\nSaMer 希望基于他已有的测试用例生成更多测试用例。他的测试用例包含一个包含 $n$ 个整数的数组 $A$，他需要找出对于每个整数 $k$（$1$ 到 $n$，包含两端），有多少个连续子数组的答案等于 $k$。\n\n输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 5000$），表示数组的大小。\n\n第二行包含 $n$ 个整数 $a_1$,$a_2$,$dots.h$,$a_n$（$-10^8 lt.eq a_i lt.eq 10^8$），表示数组的值。\n\n请输出 $n$ 个用空格分隔的整数，第 $k$ 个整数应为答案等于 $k$ 的连续子数组的数量。\n\n## Input\n\nThe first line of input contains a single integer $n$ ($1 lt.eq n lt.eq 5000$), the size of the array.The second line contains $n$ integers $a_1$,$a_2$,$dots.h$,$a_n$ ($-10^8 lt.eq a_i lt.eq 10^8$), the values of the array.\n\n## Output\n\nOutput $n$ space-separated integers, the $k$-th integer should be the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$.\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array of integers.  \nFor any integer $ x \\neq 0 $, define its *square-free signature* $ s(x) $ as the unique square-free integer such that $ x = s(x) \\cdot y^2 $ for some $ y \\in \\mathbb{Z} $.  \nDefine $ s(0) = 0 $.  \n\nFor any subarray $ A[i:j] = (a_i, a_{i+1}, \\dots, a_j) $, define a grouping of its elements such that two elements $ a_p, a_q $ may be in the same group if and only if $ s(a_p) = s(a_q) $ or $ s(a_p) \\cdot s(a_q) $ is a perfect square.  \nNote: Since $ s(x) $ is square-free, $ s(a_p) \\cdot s(a_q) $ is a perfect square if and only if $ s(a_p) = s(a_q) $.  \nThus, two elements can be in the same group **if and only if** they have the same square-free signature.\n\nTherefore, the minimum number of groups required for a subarray is equal to the number of **distinct non-zero square-free signatures** in that subarray, **plus** one group for all zeros (since $ s(0) = 0 $, and $ 0 \\cdot x = 0 $ is a perfect square for any $ x $, so all zeros can be grouped together, and zeros can be grouped with any other element).\n\nBut note: $ 0 \\cdot x = 0 $ is a perfect square, so **zero can be placed in any group** without violating the condition. Therefore, **all zeros can be placed together in one group**, and they **do not force additional groups**. However, if a non-zero element has signature $ s $, then it can be grouped with any other element having the same signature $ s $, or with zero.\n\nBut crucially: **Can a non-zero element be grouped with zero?**  \nYes, because $ 0 \\cdot a = 0 $, which is a perfect square.  \nTherefore, **all elements (zero and non-zero) can be placed in a single group** if desired — but we are minimizing the number of groups.\n\nWait: But the condition is: *the product of any pair of integers in the same group must be a perfect square*.  \nIf a group contains both zero and a non-zero element $ a $, then $ 0 \\cdot a = 0 $ is fine.  \nBut if a group contains two non-zero elements $ a $ and $ b $ with $ s(a) \\ne s(b) $, then $ a \\cdot b $ is not a perfect square (since $ s(a) \\cdot s(b) $ is square-free and not 1).  \nSo:  \n- All zeros can be grouped together.  \n- Non-zero elements must be grouped **by their square-free signature**: two non-zero elements can be in the same group **iff** they have the same square-free signature.  \n- But: **Can a zero be grouped with a non-zero element?**  \n  Yes, because $ 0 \\cdot a = 0 $ is a perfect square.  \n  So if we put **all zeros and one non-zero group** together, then:  \n  - $ 0 \\cdot 0 = 0 $ ✅  \n  - $ 0 \\cdot a = 0 $ ✅  \n  - $ a \\cdot a = a^2 $ ✅  \n  So **entirely possible** to put **all elements into one group** if we have at least one zero and at least one non-zero?  \n\nWait — what if we have two non-zero elements with different square-free signatures, and one zero?  \nCan we put all three in one group?  \nCheck pairwise products:  \n- $ a \\cdot b $: not a perfect square (since $ s(a) \\ne s(b) $) → ❌  \nSo even with zero present, **two non-zero elements with different square-free signatures cannot be in the same group**, because their product is not a perfect square.\n\nTherefore:  \n- **Non-zero elements with distinct square-free signatures must be in separate groups.**  \n- **Zeros can be added to any one of these groups** (since $ 0 \\cdot x = 0 $ is a perfect square).  \n- So the **minimum number of groups** for a subarray is equal to the **number of distinct non-zero square-free signatures** in that subarray.  \n  (Zeros can be merged into any one of these groups — they don’t require a separate group.)\n\nBut what if the subarray contains **only zeros**?  \nThen all products are $ 0 \\cdot 0 = 0 $, so one group suffices.  \nNumber of distinct non-zero square-free signatures = 0 → then number of groups = 1?  \nSo we must adjust:  \n\n**Final rule**:  \nLet $ G $ be the number of distinct non-zero square-free signatures in the subarray.  \nThen the minimum number of groups is:  \n$$\n\\begin{cases}\n1 & \\text{if } G = 0 \\text{ (all zeros)} \\\\\nG & \\text{if } G > 0\n\\end{cases}\n$$\n\nBecause:  \n- If $ G = 0 $: all elements are zero → one group.  \n- If $ G > 0 $: each distinct non-zero signature requires its own group; zeros can be merged into any one of them → total groups = $ G $.\n\n---\n\n**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\mathbb{Z} $, $ |a_i| \\le 10^8 $.  \n\nFor each $ x \\in \\mathbb{Z} $, define the *square-free signature* $ s(x) $:  \n- If $ x = 0 $, then $ s(x) = 0 $.  \n- If $ x \\ne 0 $, then $ s(x) $ is the unique square-free integer such that $ x = s(x) \\cdot k^2 $ for some $ k \\in \\mathbb{Z}^+ $, and $ s(x) \\in \\mathbb{Z} \\setminus \\{0\\} $, with no square divisor >1.  \n  (Note: $ s(x) $ can be negative; e.g., $ s(-8) = -2 $, since $ -8 = -2 \\cdot 2^2 $.)\n\nFor any contiguous subarray $ A[i:j] = (a_i, a_{i+1}, \\dots, a_j) $, define:  \n- $ G_{i,j} = \\left| \\left\\{ s(a_k) \\mid i \\le k \\le j,\\ s(a_k) \\ne 0 \\right\\} \\right| $, the number of distinct non-zero square-free signatures in the subarray.  \n\nThen the minimum number of groups for $ A[i:j] $ is:  \n$$\nf(i,j) = \n\\begin{cases}\n1 & \\text{if } G_{i,j} = 0 \\\\\nG_{i,j} & \\text{if } G_{i,j} > 0\n\\end{cases}\n$$\n\n---\n\n**Constraints**  \n1. $ 1 \\le n \\le 5000 $  \n2. $ -10^8 \\le a_i \\le 10^8 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n---\n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, n\\} $, compute:  \n$$\nc_k = \\left| \\left\\{ (i,j) \\mid 1 \\le i \\le j \\le n,\\ f(i,j) = k \\right\\} \\right|\n$$  \nOutput $ c_1, c_2, \\dots, c_n $ as space-separated integers.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF980D","tags":["dp","math","number theory"],"sample_group":[["2\n5 5","3 0"],["5\n5 -4 2 1 8","5 5 3 2 0"],["1\n0","1"]],"created_at":"2026-03-03 11:00:39"}}