总结题意
显然可以转化为序列问题嘛。
给出序列 \(A\{a_i\}\)，你需要通过若干次操作使其归零。
操作：
选定 \(d | n\)、\(k\)、\(r\)，对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。
题解
很明显，加减相互抵消，对于所有 \(d\)、\(r\) 相同的位置可以视作一次操作。
如何表示一次操作呢？
如果你还记得生成函数这个高级东西的话，这就很容易了。
先把原序列函数化，记作：
\[A(x) = \sum_{i=0}^{n-1}a_ix^i \]那么修改的增量多项式即为：
\[kf(d,r,x) \]\[f(d,r,x) = x^r\frac{1 - x ^ n}{1 - x ^ d} \]注意这里大于 \(n\) 的项可以不管他。
那么，有解当且仅当
\[\sum kf(d,r,x) = A(x) \]有解。
丢番图方程的有解判断应用裴蜀定理，则有解条件：
\[\gcd\{f(d,r,x)\} | A(x) \]谈论到这，我们发现
\[\frac{f(d,r,x)}{x^r} = f(d,0,x) \Rightarrow f(d,0,x) | f(d,r,x) \]所以 \(f(d,r,x),r\not=0\) 是没有贡献的，不用考虑。
于是我们现在令
\[f(d,x) = \frac{1 - x ^ n}{1 - x ^ d} \]有解：
\[\gcd\{f(d,x)\} | A(x) \]现在这步不是拆 \(A\) 就是拆 \(f\)，但 \(A\) 不是构造的，是输入的，所以我们讨论 \(f\)。
这里因式分解一下：
- \(x^n - 1\) 在复数域上的因式分解
设其根为 \(re^{i\theta}\)，
\[re^{i\theta} = 1 \]\[(re^{i\theta})^n = 1 \]\[r^ne^{in\theta} = 1 \times e^{i0} \]故
\[r^n = 1,n\theta = 2 \pi k,k \in Z \]\[r = 1,\theta = \frac{2k\pi}{n} \]\[x = e^{i\frac{2k\pi}{n}} = \omega_n^{k} \]显然，上式得证。
\[f(d,x) = \frac{\prod_{i=0}^{n-1} (x - \omega_n^i)}{\prod_{i=0}^{d-1} (x - \omega_d^i)} \]\[= \frac{\prod_{i=0}^{n-1} (x - \omega_n^i)}{\prod_{i=0}^{d-1} (x - \omega_n^{\frac{ni}{d}})} \]\[= \prod_{i=0}^{n-1}[\frac{n}{d} \not| i](x - \omega_n^i) \]实际上，把 \(\frac{n}{d} \not| i\) 换个形式书写就是 \(gcd(i,n) = 1\)，所以：
\[\gcd\{f(d,x)\} = \prod_{i=0}^{n-1}[gcd(i,n) = 1](x - \omega_n^i) \]不太好做，容斥一下变成算补集，构造下补集：
\[\prod_{i=0}^{n-1}[gcd(i,n) = 1](x - \omega_n^i) = \frac{x^n - 1}{\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1)} \]然后：
\[\frac{x^n - 1}{\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1)} | A(x) \]\[x^n - 1 | A(x)\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1) \]暴力循环卷积一下，算出右边。
没了。
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005], tmp[100005];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) // A(x)
{
char ch;
cin >> ch;
a[i] = ch - '0';
}
int nn = n;
for (int i = 2; i <= nn; ++i) //[(x^{n/p} - 1)]H(x)
{
if (nn % i == 0)
{
for(int j=0;j<n;j++)
{
tmp[(j + n/i) % n] = a[j] - a[(j + n/i) % n];
}
for(int j=0;j<n;j++)
{
a[j] = tmp[j];
}
while (nn % i == 0)
{
nn /= i;
}
}
}
for (int i = 0; i < n; ++i)
{
if (a[i] != 0)
{
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}