题解 CF1437F 【Emotional Fishermen】

· · 题解

题意都清楚吧

平方做法

要求排列数显然和一开始的顺序没有关系，想都不想先排个序（注意后面说的数组都是排好了序的）

然后考虑 dp：设 f_i 表示到第 i 个数的方案数。

仔细想想好像这排列的长度是固定的：必须要把 \le \dfrac{a_i}{2} 的数加入进来，并且，更大的也加不进来。于是这个排列的长度就是 \le \dfrac{a_i}{2} 的数个数，设为 mx（mx 的含义可以理解为，最大的 j 使得 2a_j\le a_i），再 +1 （算自己）

然后想怎么转移。枚举在前面放到哪个位置 j，这个方案数是 f_j，并且占用了 mx_j+1 个位置；然后现在还剩下 (n-1)-(mx_j+1) 个位置，放剩下的 mx_i-(mx_j+1) 个数。这些放在 a_i 后面。注意到，因为有 a_i 的存在，它们咋放都行，然后就用 A 来算了。

于是

f_i=\sum\limits_{j} f_j A_{n-mx_j-2}^{mx_i-mx_j-1}

优化

注意到我们算 A 的时候是： \dfrac{n!}{(n-m)!}

然后这个 n,m 具有一个相同的 -(mx_j+1)，那么分母上就会约掉

注意到这一点，考虑来推推式子，变成：

\dfrac{(n-mx_j-2)!}{(n-1-mx_i)!} f_j

一部分只和 j 有关，一部分只和 i 有关，就前缀和优化就行了

复杂度 O(n) （不算排序）

代码

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N   5140
    #define mod 998244353
    #define int long long
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define all(a) a.begin(),a.end()
    #define iter(a,p) (a.begin()+p)
    int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
    template <typename T> void Rd(T& arg){arg=I();}
    template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
    void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}
    int n,a[N];
    void Input()
    {
        n=I(); F(i,1,n) a[i]=I();
    }
    int fc[N],fi[N],iv[N]; // 阶乘，阶乘逆元，逆元
    void Init()
    {
        fc[0]=fc[1]=fi[0]=fi[1]=iv[1]=1;
        F(i,2,n) iv[i]=iv[mod%i]*(mod-mod/i)%mod,fi[i]=fi[i-1]*iv[i]%mod,fc[i]=fc[i-1]*i%mod;
    }
    int qpow(int a,int b,int m=mod) {int r=1; while(b) {if (b&1) r=r*a%m; a=a*a%m,b>>=1;} return r;}
    int A(int n,int m) {return fc[n]*fi[n-m]%mod;}

    int f[N],len[N];
    int sum[N];
    void Soviet()
    {
        Init();

        sort(a+1,a+n+1);
        if (a[n]<a[n-1]*2) {puts("0"); return;}
        int mx=0;
        f[0]=1; sum[0]=fc[n-1]%mod;
        F(i,1,n)
        {
            while(2*a[mx]<=a[i] and mx<=n) ++mx; --mx;
            len[i]=mx+1;
            // len: 排列长度=mx+1

            // F(j,0,mx) f[i]=(f[i]+f[j]*A(n-1-len[j],mx-len[j]))%mod;
            // ↑ 这个是暴力写法
            /*
            A(n-1-len[j],mx-len[j])*f[j]
            fi[n-1-mx]  * fc[n-1-len[j]]*f[j]
            ↑ 只和i有关    ↑ 只和j有关
            */
            f[i]=(f[i]+fi[n-len[i]]*sum[mx]%mod)%mod;
            sum[i]=(sum[i-1]+fc[n-1-len[i]]*f[i]%mod)%mod;
        }
        printf("%lld\n",f[n]);
    }
    void IsMyWife()
    {
        Input();
        Soviet();
    }
}
#undef int //long long
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();
    return 0;
}