[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]C Crazy Rotations

    题目大意：给你一个由'R' 'B' 'Y'组成的长度为n的字符串S，操作k表示将字符串的最后k位移到字符串的开头。定义一个操作k的craziness为原串进行操作k之后，形成的字符串与原串相同位置不同字符的位置数目。要求你构造一个由操作序列，为1...n-1的一个全排列，使得第i位上的操作数目递增。

    题解：构造三个函数\[R(x)=a_0+a_1x^1+a_2x^2+...+a_{n-1}x^{n-1}\]\[B(x)=b_0+b_1x^1+b_2x^2+...+b_{n-1}x^{n-1}\]\[Y(x)=c_0+c_1x^1+c_2x^2+...+c_{n-1}x^{n-1}\]

    其中\(S_i='R'\)时\(a_i=1\),\(S_i='B'\)时\(b_i=1\),\(S_i='Y'\)时\(c_i=1\)，其余各项为0。

    \(A(x)*A^-1(x)\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const double pi=M_PI;
const int DEBUG=1;

struct Complex
{
	double r,i;
	Complex (double _r=0,double _i=0):r(_r),i(_i){}
	friend Complex operator + (const Complex &a,const Complex &b);
	friend Complex operator - (const Complex &a,const Complex &b);
	friend Complex operator * (const Complex &a,const Complex &b);
};

Complex operator + (const Complex &a,const Complex &b) {return Complex(a.r+b.r,a.i+b.i);}
Complex operator - (const Complex &a,const Complex &b) {return Complex(a.r-b.r,a.i-b.i);}
Complex operator * (const Complex &a,const Complex &b) {return Complex(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}

int rev[maxn<<2];
int N;

void FFT(Complex *arr,int ctr)
{
	for (int i=0;i<N;i++) if (i<rev[i]) swap(arr[i],arr[rev[i]]);
	for (int i=1;i<N;i<<=1)
	{
		Complex wn(cos(pi/i),ctr*sin(pi/i));
		for (int j=0;j<N;j+=(i<<1))
		{
			Complex w(1,0);
			for (int k=0;k<i;k++,w=w*wn)
			{
				Complex x=arr[j+k],y=w*arr[j+k+i];
				arr[j+k]=x+y;arr[j+k+i]=x-y;
			}
		}
	}
	if (ctr==-1) for (int i=0;i<N;i++) arr[i].r/=N;
}

char ch[maxn];
Complex a[maxn<<2],a0[maxn<<2],b[maxn<<2],b0[maxn<<2],c[maxn<<2],c0[maxn<<2];
long long cnt[maxn];
int Rank[maxn];
int n,p;

bool cmp(const int &a,const int &b) {return cnt[a]>cnt[b];}

int main()
{
	scanf("%d%d\n",&n,&p);
	scanf("%s",ch);
	for (int i=0;i<n;i++)
		if (ch[i]=='R') a[i].r=1;
		else if (ch[i]=='B') b[i].r=1;
		else if (ch[i]=='Y') c[i].r=1;
	for (int i=0;i<n;i++) a0[i]=a[n-i-1],b0[i]=b[n-i-1],c0[i]=c[n-i-1];
	N=1;
	while (N<(n<<1)) N<<=1;
	for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
	FFT(a,1);FFT(a0,1);
	FFT(b,1);FFT(b0,1);
	FFT(c,1);FFT(c0,1);
	for (int i=0;i<N;i++) a[i]=a[i]*a0[i],b[i]=b[i]*b0[i],c[i]=c[i]*c0[i];
	FFT(a,-1);
	FFT(b,-1);
	FFT(c,-1);
	for (int i=1;i<n;i++) cnt[i]=(int)(a[n-1+i].r+a[i-1].r+0.1)+(int)(b[n-1+i].r+b[i-1].r+0.1)+(int)(c[n-1+i].r+c[i-1].r+0.1);
	for (int i=1;i<n;i++) Rank[i]=i;
	sort(Rank+1,Rank+n,cmp);
	for (int i=1;i<n;i++)
	{
		int r=i,minv=Rank[i];
		while (r<n-1 && cnt[Rank[i]]==cnt[Rank[r+1]]) minv=min(minv,Rank[++r]);
		if (r>=p) {printf("%d\n",minv);return 0;}
		i=r;
	}
}