题解：CF2038F Alternative Platforms

题意：给定 a,b 两个序列，定义某个 \{1,2,\cdots,n\} 的子集 S 的权值为：

求大小为 k 的所有子集的权值和。

考虑某个 a_i 作为答案产生贡献，此时 S 需要满足什么。首先要有 \forall x \in S, \, a_x \ge a_i，其次，如果 b_i > a_i，则额外要求 \exist x \in S \text{ s.t. } b_x \le a_i。因此我们需要排除掉 \min{b_j} > a_i 的 S，这可以通过二维数点数出。交换 a,b 后同理。那我们的贡献全部变成了诸如给定一个 i，则对所有的 j \le i 产生系数为 \binom {i}{j} 的贡献。

转化一下，可以变成给定一个 v_i，对每个 i 求出 \sum_{j \ge i} \binom{j} {i}v_j。

拆开后不难发现，设：

，则 \dfrac {[x^i] F \cdot G}{i!} 即为答案。

复杂度瓶颈在二维数点和卷积，是 O(n \log n) 的。

struct Node
{
    int v, r;
    int id;
} a[ MAXN ];
mint v[ MAXN ];
mint res[ MAXN ];
int main()
{
    cin.tie( 0 );
    int n;
    cin >> n;
    init( n );
    for ( int i = 1; i <= n; i++ )
    {
        a[ i ].id = i;
        cin >> a[ i ].v;
    }
    for ( int i = 1; i <= n; i++ )
    {
        cin >> a[ i ].r;
        M = max( M, a[ i ].r + 1 );
    }
    sort( a + 1, a + n + 1,
          [&]( Node a, Node b ) { return ( a.v == b.v ? a.id < b.id : a.v > b.v ); } );
    for ( int i = 1; i <= n; i++ )
    {
        int ct = i - 1 - T.query( a[ i ].v );
        if ( a[ i ].r <= a[ i ].v )
        {
            v[ i - 1 ] += a[ i ].v;
        }
        else
        {
            v[ i - 1 ] += a[ i ].v;
            v[ ct ] -= a[ i ].v;
        }
        T.add( a[ i ].r, 1 );
    }
    T.init();
    sort( a + 1, a + n + 1,
          [&]( Node a, Node b ) { return ( a.r == b.r ? a.id < b.id : a.r > b.r ); } );
    for ( int i = 1; i <= n; i++ )
    {
        int ct = i - 1 - T.query( a[ i ].r - 1 );
        if ( a[ i ].v < a[ i ].r )
        {
            v[ i - 1 ] += a[ i ].r;
        }
        else
        {
            v[ i - 1 ] += a[ i ].r;
            v[ ct ] -= a[ i ].r;
        }
        T.add( a[ i ].v, 1 );
    }
    vector< mint > f( n + 1 );
    vector< mint > g( n + 1 );
    for ( int i = 0; i <= n; i++ )
    {
        f[ i ] = v[ i ] * fac[ i ];
        g[ i ] = ifac[ n - i ];
    }
    vector< mint > h = multiple( f, g );
    for ( int i = 0; i < n; i++ )
    {
        res[ i + 1 ] = h[ i + n ] * ifac[ i ];
    }
    for ( int i = 1; i <= n; i++ )
    {
        res[ i ] = res[ i ] * qpow( C( n, i ), pmod - 2 );
        cout << raw( res[ i ] ) << " ";
    }
    cout << endl;
}