5322: [Jxoi2018]排序问题

链接

分析：

　　每次选一个出现次数最小的。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#define pa pair<int,int>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int mod = ;

int fac[], a[], b[];

int ksm(int a,int b) {

    int res = ;

    while (b) {

        if (b & ) res = 1ll * res * a % mod;

        a = 1ll * a * a % mod;

        b >>= ;

    }

    return res;

}

void solve() {

    int n = read(), m = read(), l = read(), r = read(), tot = , cnt = , f = r - l + , ans = ;

    for (int i = ; i <= n; ++i) a[i] = read();

    sort(a + , a + n + );

    for (int i = , j = ; i <= n; i = j) {

        while (j <= n && a[i] == a[j]) j ++;

        if (l <= a[i] && a[i] <= r) b[++tot] = j - i, f --;

        else ans = 1ll * ans * fac[j - i] % mod;

    }

    sort(b + , b + tot + );

    for (int i = , j = ; i <= tot; i = j) {

        while (j <= tot && b[i] == b[j]) j ++;

        ++cnt; a[cnt] = b[i], b[cnt] = j - i;

    }

    a[++cnt] = 1e9, b[cnt] = ;

    for (int i = , M = m; i <= cnt; ++i) {

        LL c = a[i] - a[i - ], t = c * f;

        if (t > M) {

            int x = a[i - ] + (M / f), y = M % f;

            ans = 1ll * ans * ksm(fac[x], f - y) % mod * ksm(fac[x + ], y) % mod;

            for (int j = i; j < cnt; ++j)

                ans = 1ll * ans * ksm(fac[a[j]], b[j]) % mod;

            break;

        }

        M -= t, f += b[i];

    }

    ans = 1ll * fac[n + m] * ksm(ans, mod - ) % mod;

    printf("%d\n", ans);

}

int main() {

    fac[] = ;

    for (int i = ; i <= ; ++i) fac[i] = 1ll * fac[i - ] * i % mod;

    for (int T = read(); T --; solve());

    return ;

}