E - K-Inversions Gym - 101002E（FFT）

71 阅读 0 评论 47 点赞

我是靠谱客的博主和谐冬日，最近开发中收集的这篇文章主要介绍E - K-Inversions Gym - 101002E（FFT），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

题意：
K-inversions的意思是存在(i,j)，满足 j - i = k且 s[i]=B ,s[j]=A.
求所有的K-inversions数目

思路：
真没想到是FFT，这玩意就去年10月打gym写过一次。经学长提醒感觉确实很裸。
FFT具体怎么证明可以不管，但是你需要知道，这是用来优化多项式乘法的（合并多项式应该都写过？）。

本题中，只需要设置’A‘为 $x^i$ ，设置’B’为 $x^{len-j}$ ，那么最后多项式相乘的结果就是 $x^{len+j-i}$ ，这实际上就表示 $(j - i) - i n v e r s i o n$ 。求出所有大于len的项就是结果。

直接套用了洛谷上的模板：https://www.luogu.com.cn/problem/P3803

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN=3e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const double Pi=acos(-1.0);
struct complex
{
    double x,y;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){ return complex(a.x+b.x , a.y+b.y);}
complex operator - (complex a,complex b){ return complex(a.x-b.x , a.y-b.y);}
complex operator * (complex a,complex b){ return complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}//不懂的看复数的运算那部分
int N,M;
int l,r[MAXN];
int limit=1;
void fast_fast_tle(complex *A,int type)
{
    for(int i=0;i<limit;i++)
        if(i<r[i]) swap(A[i],A[r[i]]);//求出要迭代的序列
    for(int mid=1;mid<limit;mid<<=1)//待合并区间的中点
    {
        complex Wn( cos(Pi/mid) , type*sin(Pi/mid) ); //单位根
        for(int R=mid<<1,j=0;j<limit;j+=R)//R是区间的右端点，j表示前已经到哪个位置了
        {
            complex w(1,0);//幂
            for(int k=0;k<mid;k++,w=w*Wn)//枚举左半部分
            {
                complex x=A[j+k],y=w*A[j+mid+k];//蝴蝶效应
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}

char s[MAXN];

void init() {
    scanf("%s",s + 1);
    int len = strlen(s + 1);
    int N = len,M = len;
    for(int i = 1;i <= len;i++) {
        if(s[i] == 'A') {
            a[i].x = 1;
        }
        else {
            b[len - i].x = 1;
        }
    }
    
    while(limit<=N+M) limit<<=1,l++;
    for(int i=0;i<limit;i++)
        r[i]= ( r[i>>1]>>1 )| ( (i&1)<<(l-1) ) ;
    // 在原序列中 i 与 i/2 的关系是 ： i可以看做是i/2的二进制上的每一位左移一位得来
    // 那么在反转后的数组中就需要右移一位，同时特殊处理一下复数
    fast_fast_tle(a,1);
    fast_fast_tle(b,1);
    for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];
    fast_fast_tle(a,-1);
    for(int i=len + 1;i<=N+M - 1;i++)
        printf("%d ",(int)(a[i].x/limit+0.5));
    
    
}

int main()
{
    init();
    return 0;
}