专栏文章

为什么 FFT 的 $O(n^2\log n)$ 可以过 $5000$

EETO_leader
CF2084E题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipp6llj
此快照首次捕获于
2025/12/03 15:40
3 个月前
此快照最后确认于
2025/12/03 15:40
3 个月前
查看原文
非官方做法，图一乐
想了 1h 没有别的 idea 写了个感觉过不了一点的 FFT O(n2log⁡n)\sout{O(n^2\log n)} 过了 /ll。早知道就直接写了。

题意简述

给你一个部分位置确定的排列，定义一个排列的代价为：
∑l=1n∑r=lnMEX(pl,…,pr)\sum\limits_{l=1}^n\sum\limits_{r=l}^n \text{MEX}(p_l,\dots,p_r)
问所有可能的排列的代价和。

Solution

考虑对每个 kk 对满足 MEX(pl,⋯ ,pr)≥k\text{MEX}(p_l,\dotsm,p_r)\ge k 的 (p,l,r)(p,l,r) 三元组数量求和。
定义 c(l,r)c(l,r) 表示 [l,r][l,r] 中还没确定的位置个数。
定义 h(l,r,k)h(l,r,k) 表示 [l,r][l,r] 的答案是否可以为 kk。
定义 q(k)q(k) 表示未确定的 ≤k\le k 的元素个数。
则
Ans=∑l=1n∑r=ln∑k=1nh(l,r,k)(c(l,r)q(k))q(k)!(c(1,n)−q(k))!Ans=\sum\limits_{l=1}^n\sum\limits_{r=l}^n\sum\limits_{k=1}^{n} h(l,r,k)\binom{c(l,r)}{q(k)}q(k)!(c(1,n)-q(k))!
考虑优化
q(k)=kq(k)=k 的情况直接 dp 是好做的。
剩下的情况发现 h(l,r,k)=1h(l,r,k)=1 是只需要 [l′,r′]⊂[l,r][l',r']\subset [l,r]，其中 [l′,r′][l',r'] 是最小满足每个确定的 ≤k\le k 的元素位置都包含的区间。
然后修改一下式子
∑l=1l′∑r=r′n∑k=1n(c(l,l′−1)+c(l′,r′)+c(r′+1,r)q(k))q(k)!(c(1,n)−q(k))!\sum\limits_{l=1}^{l'}\sum\limits_{r=r'}^{n}\sum\limits_{k=1}^n \binom{c(l,l'-1)+c(l',r')+c(r'+1,r)}{q(k)}q(k)!(c(1,n)-q(k))!\\
容易发现可以用 FFT 优化。
时间复杂度 O(n2log⁡n)O(n^2\log n)，我也不知道为什么能过。
CPP
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto MOD=(int)(1e9+7);
class mathbase{
private:
    vector<lint> fct,ifct;
public:
    constexpr auto qpow(lint a,auto b) const{
        auto res=1ll;
        while(b){
            if(b&1) (res*=a)%=MOD;
            (a*=a)%=MOD;b>>=1;
        }
        return res;
    }
    constexpr auto inv(auto x) const{return qpow(x,MOD-2);}
    auto init(const auto n){
        fct.resize(n,1);
        cir(i,1,n) fct[i]=fct[i-1]*i%MOD;
        ifct.resize(n);
        ifct[n-1]=inv(fct[n-1]);
        for(auto i=n-2;~i;--i) ifct[i]=ifct[i+1]*(i+1)%MOD;
    }
    auto C(const auto a,const auto b) const{
        if(a<b||b<0) return 0ll;
        return fct[a]*ifct[b]%MOD*ifct[a-b]%MOD;
    }
    auto fact(const auto x) const{return x>-1?fct[x]:0;}
} math;
using complf=complex<double>;
class basic_poly{
private:
    static constexpr auto pi=acosl(-1);
    auto change(vector<complf>&a,const int n){
        vector<int> rev(n);
        cir(i,0,n) rev[i]=((rev[i>>1]>>1)|((n>>1)*(i&1)));
        cir(i,0,n) if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    template<const int type>
    auto fft(vector<complf>&a,const int n){
        change(a,n);
        for(auto h=2;h<n+1;h<<=1){
            const auto midh=h/2;
            const auto wx=complf(cos(pi*2/h),sin(pi*2*type/h));
            for(auto i=0;i<n;i+=h){
                auto u=complf(1,0);
                cir(k,i,i+midh){
                    const auto wy=u*a[k+midh];
                    a[k+midh]=a[k]-wy;a[k]+=wy;
                    u*=wx;
                }
            }
        }
        if(type==-1) for(auto&i:a) i/=n;
    }
public:
    auto mul(vector<lint> a,vector<lint> b){
        const auto n=1<<((int)(log2(a.size()+b.size()))+1);
        vector<complf> fx(n);
        cir(i,0,(int)(a.size())) fx[i]+=complf(a[i],0);
        cir(i,0,(int)(b.size())) fx[i]+=complf(0,b[i]);
        fft<1>(fx,n);
        for(auto&i:fx) i*=i;
        fft<-1>(fx,n);
        vector<lint> res(n);
        cir(i,0,n) res[i]=roundl(fx[i].imag()/2);
        return res;
    }
} poly;
static constexpr auto maxn=5007;
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int T;cin>>T;
    math.init(maxn);
    while(T--) [&]{
        int n;cin>>n;vector<int> a(n);
        for(auto&i:a) cin>>i;
        const auto m=ranges::count(a,-1);
        vector<lint> cur(m+1);
        vector<lint> qans(m+1);
        cir(i,0,n){
            if(a[i]==-1){
                for(auto i=m;i;--i) (cur[i]+=cur[i-1])%=MOD;
                (++cur[1])%=MOD;
            }
            ++cur[0];
            cir(i,0,m+1) (qans[i]+=cur[i])%=MOD;
        }
        auto ans=0ll;
        vector<int> pos(n,-1);
        cir(i,0,n) if(a[i]>-1) pos[a[i]]=i;
        cir(w,1,n+1){
            auto l=n,r=0,cnt=0;
            cir(x,0,w) if(pos[x]>-1){
                l=min(l,pos[x]);
                r=max(r,pos[x]);
            }else{
                ++cnt;
            }
            if(l>r){
                cir(c,cnt,cnt+1) (ans+=qans[c]*math.fact(m-c)%MOD*math.fact(c))%=MOD;
            }else{
                auto mc=0;
                cir(i,l,r+1) mc+=(a[i]==-1);
                vector<lint> al(l+1),ar(n-r+1);
                auto wcnt=0;
                al[0]=ar[0]=1;
                for(auto i=l-1;~i;--i) wcnt+=(a[i]==-1),++al[wcnt];
                wcnt=0;
                cir(i,r+1,n) wcnt+=(a[i]==-1),++ar[wcnt];
                const auto res=poly.mul(al,ar);
                cir(i,0,(int)(res.size())) if(res[i]) (ans+=(res[i]%MOD)*math.C(i+mc,cnt)%MOD*math.fact(m-cnt)%MOD*math.fact(cnt))%=MOD;
            }
        }
        cout<<ans<<'\n';
    }();
    return 0;
}
令人忍俊不禁。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...