• 欢迎光临~

CF859G Circle of Numbers 解题报告

开发技术 开发技术 2022-10-11 次浏览

CF859G Circle of Numbers 解题报告:

更好的阅读体验

题意

有一个长度为 (n) 的圆环,每个整点位置都有一个整数 (in{0,1}),你可以选择一个 (cmid n) 以及一个 (d<c),将所有 (kc+d) 位置的数同时加、减一个实数 (r),求是否可以将所有数字归零。

(1leqslant nleqslant 10^5)

分析

没做过这种类型的题。。。也不太会分圆多项式那一套理论。

首先将圆环的状态(从 (0) 开始)写成生成函数 (F(x)),那么一次操作就是将 (F(x)) 加上 (fx^cfrac{1-x^n}{1-x^d})

考虑多项式环上的裴蜀定理,那么合法当且仅当 (gcd_{dmid n}{frac{1-x^n}{1-x^d}}mid F(x))

利用单位根展开:

[frac{1-x^n}{1-x^d}=frac{prod_{k=0}^{n-1}(x-omega_n^k)}{prod_{k=0}^{d-1}(x-omega_d^k)}=prod_{k=0}^{n-1}[frac{n}{d}notmid k](x-omega_n^k) ]

[P(x)=gcd_{dmid n}{frac{1-x^n}{1-x^d}}=prod_{k=0}^{n-1}[gcd(k,n)=1](x-omega_n^k) ]

互素的条件很难处理,于是考虑其补:(Q(x)=prod_{k=0}^{n-1}[gcd(k,n)>1](x-omega_n^k)),由于 (P(x)Q(x)=x^n-1),所以若 (P(x)mid F(x)) 则有 (x^n-1mid F(x)Q(x)),这就是一个循环卷积。

(Q(x)) 卷积仍然很麻烦,但我们只需利用 (Q(x)) 不包含 ([gcd(k,n)=1](x-omega_n^k)) 的性质,写出 (R(x)=prod_{pintext{Prime},pmid n}(x^{frac np}-1))。判别方式不变,而卷积复杂度降至 (O(nomega(n))),可以通过。

代码

#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=100005;
int n,ans;
int f[maxn],g[maxn];
string s;
int main(){
	scanf("%d",&n),cin>>s;
	for(int i=0;i<n;i++)
		f[i]=s[i]-48;
	for(int v=n,p=2;p<=v;p++)
		if(v%p==0){
			while(v%p==0)
				v/=p;
			for(int i=0;i<n;i++)
				g[i]=f[(i-n/p+n)%n]-f[i];
			for(int i=0;i<n;i++)
				f[i]=g[i];
		}
	for(int i=0;i<n;i++)
		ans|=f[i];
	puts(ans==0? "YES":"NO");
	return 0;
}
程序员灯塔
转载请注明原文链接:CF859G Circle of Numbers 解题报告
喜欢 (0)