小于x的赋值为1，否则为0

区间等于k的个数

求0~n连续的n+1个k？

N<=1e5?

FFT！

考虑卷积建模：用下标相加实现转移到位，数值相乘类比乘法原理！

法一：

分治，然后FFT没了

法二：

不分治也可以！区间查询->前缀相减

ans[j-i]=f[j]*f[i]，f[i]表示数值为i的前缀和个数

减法怎么办？

reverse变成加法！

i->n-i

ans[j-i]=f[j]*f[i]=f[j]*f'[n-i]

FFT一下，n+j-i位置的值就是ans辣

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const double Pi=acos(-1);const int N=2e5+5;struct po{    double x,y;    po(){}    po(double xx,double yy){        x=xx;y=yy;    }    po friend operator +(po a,po b){        return po(a.x+b.x,a.y+b.y);    }    po friend operator -(po a,po b){        return po(a.x-b.x,a.y-b.y);    }    po friend operator *(po a,po b){        return po(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);    }}a[4*N],b[4*N];int c[N],s[N];int n,x;int rev[4*N];ll ans[N];void fft(po *f,int c){    for(reg i=0;i
      
       >1]>>1)|((i&1)?(n>>1):0);    }//    for(reg i=1;i<=lp;++i){//        cout<
       
        <<" ";//    }cout<
       
      
     

 

reverse想法比较有意思！

值得注意！