{"raw_statement":[{"iden":"statement","content":"_n_ evenly spaced points have been marked around the edge of a circle. There is a number written at each point. You choose a positive real number _k_. Then you may repeatedly select a set of 2 or more points which are evenly spaced, and either increase all numbers at points in the set by _k_ or decrease all numbers at points in the set by _k_. You would like to eventually end up with all numbers equal to 0. Is it possible?\n\nA set of 2 points is considered evenly spaced if they are diametrically opposed, and a set of 3 or more points is considered evenly spaced if they form a regular polygon."},{"iden":"input","content":"The first line of input contains an integer _n_ (3 ≤ _n_ ≤ 100000), the number of points along the circle.\n\nThe following line contains a string _s_ with exactly _n_ digits, indicating the numbers initially present at each of the points, in clockwise order."},{"iden":"output","content":"Print \"_YES_\" (without quotes) if there is some sequence of operations that results in all numbers being 0, otherwise \"_NO_\" (without quotes).\n\nYou can print each letter in any case (upper or lower)."},{"iden":"examples","content":"Input\n\n30\n000100000100000110000000001100\n\nOutput\n\nYES\n\nInput\n\n6\n314159\n\nOutput\n\nNO"},{"iden":"note","content":"If we label the points from 1 to _n_, then for the first test case we can set _k_ = 1. Then we increase the numbers at points 7 and 22 by 1, then decrease the numbers at points 7, 17, and 27 by 1, then decrease the numbers at points 4, 10, 16, 22, and 28 by 1."}],"translated_statement":[{"iden":"statement","content":"#cf_span[n] 个均匀分布的点被标记在圆周上。每个点上有一个数字。你选择一个正实数 #cf_span[k]。然后你可以反复选择一个包含 #cf_span[2] 个或更多点的集合，这些点均匀分布，并将集合中所有点的数字都增加 #cf_span[k] 或都减少 #cf_span[k]。你希望最终所有数字都变为 #cf_span[0]。这是否可能？\n\n一个包含 #cf_span[2] 个点的集合被认为是均匀分布的，如果它们是直径对置的；一个包含 #cf_span[3] 个或更多点的集合被认为是均匀分布的，如果它们构成一个正多边形。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100000])，即圆周上的点数。\n\n接下来的一行包含一个恰好有 #cf_span[n] 个数字的字符串 #cf_span[s]，按顺时针顺序表示每个点上初始的数字。\n\n如果存在某种操作序列能使所有数字变为 #cf_span[0]，则输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（不含引号）。\n\n你可以以任意大小写形式输出每个字母。\n\n如果我们从 #cf_span[1] 到 #cf_span[n] 给点编号，那么对于第一个测试用例，我们可以设 #cf_span[k = 1]。然后我们增加点 #cf_span[7] 和 #cf_span[22] 上的数字各 #cf_span[1]，接着减少点 #cf_span[7]、#cf_span[17] 和 #cf_span[27] 上的数字各 #cf_span[1]，再减少点 #cf_span[4]、#cf_span[10]、#cf_span[16]、#cf_span[22] 和 #cf_span[28] 上的数字各 #cf_span[1]。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100000])，即圆周上的点数。接下来的一行包含一个恰好有 #cf_span[n] 个数字的字符串 #cf_span[s]，按顺时针顺序表示每个点上初始的数字。"},{"iden":"output","content":"如果存在某种操作序列能使所有数字变为 #cf_span[0]，则输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（不含引号）。你可以以任意大小写形式输出每个字母。"},{"iden":"examples","content":"输入3000100000100000110000000001100输出YES输入6314159输出NO"},{"iden":"note","content":"如果我们从 #cf_span[1] 到 #cf_span[n] 给点编号，那么对于第一个测试用例，我们可以设 #cf_span[k = 1]。然后我们增加点 #cf_span[7] 和 #cf_span[22] 上的数字各 #cf_span[1]，接着减少点 #cf_span[7]、#cf_span[17] 和 #cf_span[27] 上的数字各 #cf_span[1]，再减少点 #cf_span[4]、#cf_span[10]、#cf_span[16]、#cf_span[22] 和 #cf_span[28] 上的数字各 #cf_span[1]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 100000 $, be the number of evenly spaced points on a circle.  \nLet $ s \\in \\{0,1,\\dots,9\\}^n $ be a string of $ n $ digits, representing initial values $ a_0, a_1, \\dots, a_{n-1} \\in \\mathbb{Z} $ at points $ 0 $ to $ n-1 $ (clockwise).  \nLet $ k \\in \\mathbb{R}^+ $ be a chosen step size.  \n\nA *regular arithmetic progression modulo $ n $* is a subset of points $ \\{ i, i+d, i+2d, \\dots, i+(m-1)d \\} \\mod n $, for some $ d \\in \\{1,2,\\dots,n-1\\} $, $ m \\geq 2 $, such that the points form a regular $ m $-gon (i.e., $ m \\mid n $ and $ d = n/m $).  \n\n**Constraints**  \n1. $ n \\geq 3 $  \n2. $ a_i \\in \\{0,1,\\dots,9\\} $ for all $ i \\in \\{0,1,\\dots,n-1\\} $  \n3. Operations: choose any regular arithmetic progression of size $ m \\geq 2 $, and add or subtract $ k $ to all values at points in the progression.  \n\n**Objective**  \nDetermine whether there exists a $ k > 0 $ and a finite sequence of such operations such that all $ a_i $ become $ 0 $.  \n\n**Equivalent Reformulation**  \nLet $ \\mathcal{D} = \\{ d \\mid d = n/m, \\, m \\geq 2, \\, m \\mid n \\} $.  \nFor each $ d \\in \\mathcal{D} $, define the $ d $-cosets:  \n$ C_{d,j} = \\{ j + td \\mod n \\mid t \\in \\mathbb{Z} \\} $, for $ j = 0,1,\\dots,d-1 $.  \n\nEach operation adds $ \\pm k $ to all elements of one coset $ C_{d,j} $.  \n\nThe problem reduces to:  \nDoes there exist $ k > 0 $ and integers $ x_{d,j} \\in \\mathbb{Z} $ (net number of times we add $ +k $ minus $ -k $ on coset $ C_{d,j} $) such that:  \n$$\n\\sum_{\\substack{d \\in \\mathcal{D} \\\\ j=0}}^{d-1} x_{d,j} \\cdot \\mathbf{1}_{i \\in C_{d,j}} \\cdot k = -a_i \\quad \\forall i \\in \\{0,1,\\dots,n-1\\}\n$$\n\nEquivalently, the vector $ \\mathbf{a} = (a_0, \\dots, a_{n-1}) $ must lie in the $ \\mathbb{Z} $-span (over $ \\mathbb{R} $) of the characteristic vectors of all regular cosets $ C_{d,j} $, scaled by $ k $.  \n\n**Key Insight**  \nSince operations are linear and additive, and $ k $ is a scalar multiplier, the necessary and sufficient condition is that the vector $ \\mathbf{a} $ lies in the $ \\mathbb{Q} $-vector space generated by the characteristic vectors of all regular $ m $-gon cosets (for $ m \\mid n $, $ m \\geq 2 $).  \n\nBut since $ a_i \\in \\mathbb{Z} $, and operations use a common $ k $, we can scale:  \nLet $ \\mathcal{V} \\subseteq \\mathbb{R}^n $ be the vector space spanned over $ \\mathbb{Q} $ by all characteristic vectors of regular cosets.  \nThen:  \n> **Answer is YES** if and only if $ \\mathbf{a} \\in \\mathcal{V} $.  \n\nHowever, a deeper number-theoretic structure applies:  \n\nLet $ \\omega = e^{2\\pi i / n} $.  \nThe space $ \\mathcal{V} $ is the direct sum of the eigenspaces of the cyclic shift operator corresponding to divisors $ d \\mid n $, $ d < n $.  \n\nThe necessary and sufficient condition is:  \n> The discrete Fourier transform $ \\hat{a}_\\ell = \\sum_{j=0}^{n-1} a_j \\omega^{j\\ell} $ satisfies $ \\hat{a}_\\ell = 0 $ for all $ \\ell $ such that $ \\gcd(\\ell, n) = 1 $.  \n\n**Final Formal Statement**  \n\n**Definitions**  \nLet $ n \\in \\mathbb{Z}_{\\geq 3} $, $ \\mathbf{a} = (a_0, a_1, \\dots, a_{n-1}) \\in \\mathbb{Z}^n $.  \nLet $ \\omega = e^{2\\pi i / n} $.  \nFor $ \\ell = 0, 1, \\dots, n-1 $, define the DFT:  \n$$\n\\hat{a}_\\ell = \\sum_{j=0}^{n-1} a_j \\omega^{j\\ell}\n$$\n\n**Objective**  \nDetermine whether $ \\hat{a}_\\ell = 0 $ for all $ \\ell \\in \\{1, 2, \\dots, n-1\\} $ such that $ \\gcd(\\ell, n) = 1 $.  \n\nIf yes, output \"YES\"; otherwise, \"NO\".","simple_statement":null,"has_page_source":false}