【 HDU 5730 】 Shell Necklace - CDQ 분할 + FFT (분할 FFT)

테스트 주소: Shell Necklace 제목: 체인 모양 의 조개 목걸이 (링 이 아 닌), ai a i 가지 방안 으로 연속 i 개의 조 개 를 장식 합 니 다. 전체 목 걸 이 를 장식 하 는 데 몇 가지 방안 이 있 는 지 물 어보 세 요.방법: 이 문 제 는 CDQ 분할 + FFT (FFT 분할) 를 사용 해 야 합 니 다.먼저 f (i) f (i) 를 i 로 장 식 된 목 걸 이 를 장식 하 는 방안 수, 특수 하 게 f (0) = 1 f (0) = 1 로 하면 우 리 는 곧 상태 전이 방정식 을 얻 을 수 있다. f (i) = ＞ ij = 1f (i - j) aj f (i) = ＞ j = 1 i f (i - j) a j 는 이 방정식 을 O (n2) O (n 2) 로 직접 계산 하여 받 아들 일 수 없다.등호 오른쪽 부분 은 볼 륨 형식의 식 임 을 알 수 있 습 니 다. 그러나 이 볼 륨 은 일반 FFT 가 할 수 있 는 볼 륨 과 달리 f 자신 과 다른 배열 의 볼 륨 과 관련 되 기 때문에 우 리 는 일반적인 FFT 로 문 제 를 해결 할 수 없습니다.이때 FFT 가 나 왔 습 니 다.FFT 분할 도 CDQ 분할 + FFT 로 쓸 수 있다.우 리 는 CDQ 분 치 의 주요 사상 이 각 구간 [l, r] [l, r] 에 대한 것 을 알 고 있다. 먼저 계산 구간 [l, mid] [l, m i d] 중의 답 을 계산 한 다음 에 [l, mid] [l, m i d] 가 [mid + 1, r] [m i d + 1, r] 중의 답 에 대한 기 여 를 계산 하고 마지막 으로 계산 구간 [mid + 1, r] [m i d + 1, r] 에 대한 기 여 를 계산한다.여기 서 우 리 는 유사 한 과정 을 이용 하여 구간 [l, mid] [l, m i d] 의 모든 f f f 를 계산 한 다음 에 이 단락 의 f f 와 a 를 볼 륨 으로 하여 구간 [mid + 1, r] [m i d + 1, r] 중의 모든 f f f 의 공헌 을 구하 고 FFT 를 사용 하면 된다. 마지막 으로 구간 [mid + 1, r] [m i d + 1, r] 를 계산 하면 된다.주 정리 에 따 르 면 이 알고리즘 의 시간 복잡 도 는 O (nlog2n) O (n log 2 * 8289n) 로 이 문 제 를 통과 할 수 있 습 니 다.다음은 본인 코드 입 니 다.

#include 
using namespace std;
typedef long long ll;
const ll mod=313;
const double pi=acos(-1.0);
int n,rev[400010];
ll A[100010],f[100010];
struct Complex
{
    double x,y;
}a[400010],b[400010];
Complex operator + (Complex a,Complex b) {Complex s={a.x+b.x,a.y+b.y};return s;}
Complex operator - (Complex a,Complex b) {Complex s={a.x-b.x,a.y-b.y};return s;}
Complex operator * (Complex a,Complex b) {Complex s={a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};return s;}

void FFT(Complex *a,int type,int n)
{
    for(int i=0;iif (ifor(int mid=1;mid1)
    {
        Complex W={cos(pi/mid),type*sin(pi/mid)};
        for(int l=0;l1))
        {
            Complex w={1.0,0.0};
            for(int k=0;kif (type==-1)
    {
        for(int i=0;idouble)n;
    }
}

void solve(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;

    solve(l,mid);

    int bit=0,x=1;
    while(x1)<<1)) x<<=1,bit++;
    for(int i=0;i0.0;
    for(int i=0;i1;i++)
        a[i].x=f[l+i];
    for(int i=0;i1];
    rev[0]=0;
    for(int i=1;i>1]>>1)|((i&1)<1));
    FFT(a,1,x),FFT(b,1,x);
    for(int i=0;i1,x);

    for(int i=mid+1;i<=r;i++)
    {
        f[i]+=a[i-l-1].x+0.5;
        f[i]%=mod;
    }

    solve(mid+1,r);
}

int main()
{
    while(scanf("%d",&n)&&n)
    {
        memset(f,0,sizeof(f));
        f[0]=1;A[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&A[i]);
            A[i]%=mod;
        }
        solve(0,n);
        printf("%lld
",f[n]);
    }

    return 0;
}