题解 CF1437F 【Emotional Fishermen】

· · 题解

考虑最后的序列一定是：

\boxed{b_1} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_1}{2}\end{matrix} \boxed{b_2} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_2}{2}\end{matrix} \boxed{b_3} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_3}{2}\end{matrix}

的形式（其中 a_1\leq \frac{a_2}{2}\leq \frac{a_3}{4} \cdots） 。

将原序列从小到大排序，定义 lim_i 为最大的 j 满足 a_j\leq \frac{a_i}{2} 。

然后令 dp_i 表示 a_i\in\{b_1,b_2,\cdots\} 时，当前序列已经放入了 lim_i+1 个数的方案数。转移的时候考虑 b 序列中上一个位置是多少即可。

如果上一个位置是 j，首先肯定是将 a_i 放在当前序列的第一个非零位置，然后剩下的 lim_i-lim_j-1 个数就是在后面的空位里面乱放了：

dp_i=\sum dp_j\cdot{n-2-lim_i\choose lim_i-lim_j-1}\cdot (lim_i-lim_j-1)!

时间复杂度 O(n^2) 。

inline void solve() {
    dp[0]=1,lim[0]=-1;
    lep(i,1,n) lep(j,0,lim[i]) {
        int res=mul(C(n-lim[j]-2,lim[i]-lim[j]-1),fac[lim[i]-lim[j]-1]);
        pls(dp[i],mul(dp[j],res));
    }
    lim[n]==n-1?printf("%d\n",dp[n]):puts("0");
}

int main() {
    init();

    IN(n);
    lep(i,1,n) IN(a[i]);
    std::sort(a+1,a+1+n);

    lep(i,1,n) {
        lim[i]=lim[i-1];
        while(2*a[lim[i]+1]<=a[i]) ++lim[i];
    }
    solve();
    return 0;
}