hdu 5730 셸 목걸이 (CDQ 분할 + FFT | 다항식 구역)

제목 링크
제목 설명: i 길이 의 목 걸 이 는 a [i] a [i] 장식 방법 이 있 습 니 다. n 길이 의 목 걸 이 는 몇 가지 장식 방식 이 있 는 지 물 어보 세 요.
분석: 솔직히 나 는 이 제목 의 묘사 가 좀 애매모호 하 다 고 생각한다.
분명 한 것 은 서로 다른 방식 으로 이 서열 을 분할 하면 일정한 수량의 장식 방법 이 생 길 것 이다. 처음에 dp 방정식 을 생각 하 는 것 은 약간 어 리 석 었 다. 사실은 매우 간단 하 다. 우리 가 매 거 진 분할 의 일부분 i i.
f[n]=∑i=0nf[n−i]∗a[i] f [ n ] = ∑ i = 0 n f [ n − i ] ∗ a [ i ]
폭력 전이 시간 복잡 도 O (n2) O (n 2) 관찰 식 은 볼 륨 과 유사 한 형식 이 존재 한다. ∑ ni = 0f [n - i] ∗ a [i] ∑ i = 0 n f [n - i] ∗ a [i] 는 FFT/NTT 로 최적화 하 는 것 을 고려 할 수 있다.
dalao 들 은 좋 은 CDQ + FFT 템 플 릿 문제 라 고 말 했다.
이 문 제 는 우리 가 n 번 FFT 를 할 수 없고 반복 적 으로 계산 해서 결국 TLE 를 초래 할 것 이다.우 리 는 CDQ 분할 치 료 를 통 해 속 도 를 낸다.
CDQ 분 치 라 는 것 은 이 문제 중의 -- f [i] f [i] 를 구 하려 면 모든 f [j, j < i] f [j, j < i] 가 f [i] 에 대한 기 여 를 이용 하여 우 리 는 구간 을 다음 과 같은 두 조각 으로 나 누 었 다 [l, mid], [mid + 1, r] [l, m i d], [m i d + 1, 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]
그렇다면 우 리 는 어떻게 FFT 로 [mid + 1, r] [m i d + 1, r] 의 답 을 유지 합 니까? 우 리 는 FFT 의 원리 (다항식 곱셈) 를 회상 합 니 다.

                           4   3   2   1
                           4   3   2   1
------------------------------------------
                          1*4 1*3 1*2 1*1
                      2*4 2*3 2*2 2*1
                  3*4 3*3 3*2 3*1
              4*4 4*3 4*2 4*1

한 다항식 은 f [l], f [l + 1], f [l + 1], f [l + 2], f [l + 3],..., f [mid − 1], f [mid] f [l] f [l] [l + 1], f [l + 1], f [l + 3], f [m i d - 1], f [m i d] f [mid] f [l] f [l] f [l], f [l + 1], f [l + 1], f [l + 2], f [l + 2], f [l + 2], f [l + 2], f [l + 3],...., f [m i d - 1], f [m i d - 1], f [m i d], f [m i d] 다른 다항식 l] ∗ a [0] (f [l] ∗ a [0]) … (f[l]∗a[mid+1−l]+f[l+1]∗a[mid+1−l−1]+...)=f[mid+1] ( f [ l ] ∗ a [ m i d + 1 − l ] + f [ l + 1 ] ∗ a [ m i d + 1 − l − 1 ] + . . . ) = f [ m i d + 1 ] …
즉, 우 리 는 f [l] - f [mid] f [l] - f [m i d] 의 매개 수 를 동시에 a [0] - a [r - l] a [0] - a [r - l] 중의 매개 수 를 필요 로 하고 FFT 를 통 해 결 과 를 얻 을 수 있다.
tip
이치대로라면 FFT 의 서열 길 이 는 2 ∗ (r - l + 1) 2 ∗ (r - l + 1) 일 것 이다. 그러나 이 문제 에서 r - l + 1 r - l + 1 이면 충분 하 다.
처음에 CDQ 를 쓰 는 중 초기 화 쓰 기 는 무 너 졌 습 니 다. (초기 화 는 줄 었 습 니 다.) QwQ 를 오래 조정 하 였 습 니 다.

#include
#include
#include
#include

using namespace std;

const int p=313;
const int N=400010;
const double Pi=acos(-1.0);

struct node{
    double x,y;
    node(double xx=0,double yy=0) {
        x=xx;y=yy;
    }
};
node A[N],B[N];

node operator +(const node &A,const node &B) {return node(A.x+B.x,A.y+B.y);}
node operator -(const node &A,const node &B) {return node(A.x-B.x,A.y-B.y);}
node operator *(const node &A,const node &B) {return node(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}

int n,f[N],a[N];

void FFT(int n,node *a,int opt) {
    int i,j=0,k;
    for (i=0;iif (i>j) swap(a[i],a[j]);
        for (int l=n>>1;(j^=l)>=1);
    }
    for (int i=2;i<=n;i<<=1) {
        int m=i>>1;
        node wn(cos(2.0*opt*Pi/i),sin(2.0*opt*Pi/i));
        for (int j=0;j1,0);
            for (int k=0;kvoid CDQ(int l,int r) {
    if (l==r) {
        f[l]=(f[l]+a[l])%p;
        return;
    }
    int mid=(l+r)>>1;
    CDQ(l,mid);

    int fn=1;
    while (fn<=r-l+1) fn<<=1;

    for (int i=l;i1;i++) A[i-l]=node(f[i],0);
    for (int i=mid-l+1;i0,0);     //       fn
    for (int i=0;i1;i++) B[i]=node(a[i],0);
    for (int i=r-l+1;i0,0);
    FFT(fn,A,1); FFT(fn,B,1);
    for (int i=0;i1);
    for (int i=0;ifor (int i=mid+1;i<=r;i++) f[i]=f[i]+(int)(A[i-l].x+0.5)%p;

    CDQ(mid+1,r);
}

int main()
{
    while (scanf("%d",&n)!=EOF&&n) {
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));

        for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=p;
        CDQ(1,n);
        printf("%d
",f[n]%p);
    }
    return 0;
}

이 문 제 는 물론 간단 한 생 성 함수 해법 도 있 습 니 다. F 는 f 의 생 성 함수 (xi x i 의 계 수 는 f [i] f [i]) 이 고 A 는 a 의 생 성 함수 (xi x i 의 계 수 는 ai a i) 입 니 다.
F=F∗A+1 F = F ∗ A + 1
+ 1 은 f [0] = 1, a [0] = 0 f [0] = 1, a [0] = 0 (사실 저도 잘 모 르 겠 어 요)
F=11−A F = 1 1 − A
다항식 1 − A 1 − A 역 구 하면 된다.
좋 은 블 로 그 를 찾 았 다.
tip
식 중의 1 − A 1 − A 중의 1 은 사실 상수 항 이다.
다항식 으로 역 효 과 를 구 하 는 것 이 바로 계수 식 이다.
처음에는 제 가 직접% 313 을 했 지만 정 답 을 얻 지 못 했 습 니 다.
그래서 인터넷 에서 이 해법 의 AC 코드 는 모두 FFT 입 니 다.

//NTT AC  
#include
#include
#include
#include
#define ll long long

using namespace std;

const int N=400010;
const ll p=998244353;
const ll o=3;
int n;
ll a[N],b[N],c[N];

ll KSM(ll a,ll b) {
    ll t=1;
    while (b) {
        if (b&1) t=(t*a)%p;
        b>>=1;
        a=(a*a)%p;
    }
    return t%p;
}

void NTT(int n,ll *a,int opt) {
    int i,j=0,k;
    for (i=0;iif (i>j) swap(a[i],a[j]);
        for (int l=n>>1;(j^=l)>=1);
    }
    for (i=2;i<=n;i<<=1) {
        int m=i>>1;
        ll wn=KSM(10,(p-1)/i);
        for (j=0;j1;
            for (k=0;k<m;k++,w=(w*wn)%p) {
                ll z=(a[j+k+m]*w)%p;
                a[j+k+m]=(a[j+k]-z+p)%p;
                a[j+k]=(a[j+k]+z)%p;
            }
        }
    }
    if (opt==-1) reverse(a+1,a+n);
}

void inv(int n,ll *a,ll *b,ll *c) {
    if (n==1) {
        b[0]=KSM(a[0],p-2);
        return;
    }
    inv(n>>1,a,b,c);
    int k=n<<1;
    for (int i=0;ifor (int i=n;i0;
    NTT(k,c,1); NTT(k,b,1);
    for (int i=0;i2-b[i]*c[i]%p+p)%p*b[i]%p;
    NTT(k,b,-1);
    ll _inv=KSM(k,p-2);
    for (int i=0;i*_inv)%p;
    for (int i=n;i0; 
}

int main()
{
    while (scanf("%d",&n)!=EOF&&n) {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));

        for (int i=1;i<=n;i++) {
            ll x; scanf("%lld",&x);
            a[i]=((-x)%p+p)%p;
        }
        a[0]=1;
        int fn=1;
        while (fn<=n) fn<<=1;
        inv(fn,a,b,c);
        printf("%lld
",b[n]%313);
    }
    return 0;
}