CF1437F Emotional Fishermen

_YangZJ_ · 2023-08-31 08:22:54 · 个人记录

提供一个简单好想并且不需要用到前缀和优化的除排序外 O(n) 做法，目前提交中的最优解。

发现序列的限制条件与前缀 \max 有关，考虑将序列从小到大排序，然后从大到小将每个数插入序列中。

设 f_i 表示当前考虑到 i 的方案数，记 j 表示最靠后得一个满足 2a_j\leq a_i 的 j 。

转移分为两种：

• 将 i 放在目前序列的第一个，也就是前缀 \max 。那么 (j,i) 区间中的数既不能再作为前缀 \max ，也不能直接跟在 i 后面，其余的任意位置都可以随便放。i-1 可以放在 n-i 个数的后面，i-2 可以放在 n-i+1 个数的后面，...，j+1 可以放在 n-j-2 个数的后面，方案数为 \frac{(n-j-2)!}{(n-i-1)!} 。转移：f_i\cdot \frac{(n-j-2)!}{(n-i-1)!}\rightarrow f_j 。
• 不将 i 作为前缀 \max ，由于第一种转移保证了此时可以将 i 放在后面 n-i 个数中任意一个的后面。转移：f_i\cdot(n-i)\rightarrow f_{i-1} 。

最后的答案显然就是 f_{0} 。

code:

#include<bits/stdc++.h>
using namespace std;

const int N = 5005, P = 998244353;

inline int read() {
    int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch=='-'), ch = getchar();
    while(isdigit(ch)) x = (x*10)+(ch^48), ch=getchar(); return w?-x:x;
}

inline void inc(int &x,int y) { x += y-P; x += (x>>31)&P; }
inline int power(int a,int b) { int res = 1; for(;b;b >>= 1,a = 1ll*a*a%P) if(b&1) res = 1ll*res*a%P; return res; }

int n, a[N], f[N], fc[N], ifc[N];

signed main() {
    n = read(); fc[0] = ifc[0] = 1;
    for(int i=1;i<=n;i++) fc[i] = 1ll*i*fc[i-1]%P;
    ifc[n] = power(fc[n],P-2);
    for(int i=n-1;i>=1;i--) ifc[i] = 1ll*(i+1)*ifc[i+1]%P;
    for(int i=1;i<=n;i++) a[i] = read();
    sort(a+1,a+1+n); f[n] = 1;
    for(int i=n,j=n;i>=1;i--) {
        while(j && 2*a[j]>a[i]) --j;
        inc(f[i-1],1ll*f[i]*(n-i)%P); // 不做为前缀 max
        // 做前缀 max
        if(j==i-1) inc(f[j],f[i]); // j=i-1 特殊考虑，系数就是 1
        else if(i!=n) inc(f[j],1ll*f[i]*fc[n-j-2]%P*ifc[n-i-1]%P); 
    }
    cout<<f[0]<<endl;
    return 0;
}