CF 71C Round Table Knights 暴力

題意:一個圓上有n個點,每個點距離都相同,第i個點顔色顔色為黑色或者白色.

n<=1e5,問圓上的黑點是否能組成某個正多邊形?

假如第i個點為起點,到下一個黑點距離為d,若i,i+d,i+2d,i+kd..,i都為黑點 則存在正多邊形.

枚舉i和d,d必須為n的約數,并且距離為d時,起點有d個,暴力跳一下即可.O(n*D)(應該也可以分段來?本題似乎沒有必要.,D為因子個數)

注意對于d個起點 隻要for一次序列,記c[num]為第num個起點的結果 c[num]&=a[i] (i-num)%d==0.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20,M=505;
int n,a[N];
bool c[N];
vector<int> v;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	bool flag=false;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			v.push_back(i);
			if(i*i!=n)
				v.push_back(n/i);
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size()-1;i++)
	{
		int d=v[i];
		if(n/d<=2)
			continue;
		int num=1;
		memset(c,true,sizeof(c));
		for(int j=1;j<=n;j++)
		{
			c[num]&=a[j];
			num++;
			if(num>d)
				num=1;
		}
		for(int j=1;j<=d;j++)
		{
			if(c[j])
			{
				flag=true;
				break;
			}
		}
	}
	if(flag)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}