战斗力

题意

给定一个序列 $a_1, a_2, \ldots, a_n$，满足 $0 \le a_1 \le a_2 \le \ldots \le a_n$。求序列 $b_1, b_2, \ldots, b_n$ 的数量，满足对 $b$ 进行重新排列后可以使得 $b_i \le a_i$。

解析

显然，$b$ 满足条件，当且仅当将 $b$ 排序后有 $b_i\le a_i$。

我们有一个补集转化。设 $dp_i$ 表示只考虑排序后前 $i$ 个数的满足条件的序列 $b$ 的数量：

$$dp_i={a_n}^n-\sum_{j=0}^{i}dp_{j-1}(a_n-a_{j})^{i-j+1}\binom{i}{j-1}$$

其中，$j$ 是在枚举第一个 $b_j > a_j$ 的位置，而二项式系数 $\binom{i}{j-1}$ 选择了前 $j-1$ 个数的下标。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 1e3 + 19, mod = 1e9 + 7;

int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod, b >>= 1;
    }
    return res;
}

int n, a[maxn], dp[maxn];
int fact[maxn], ifact[maxn];

void init(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
    ifact[n] = qpow(fact[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
}

int binom(int n, int m){
    return (ll)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}

int main(){
    init(1000);

    int T; std::scanf("%d", &T);    
    while(T--){
        std::scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            std::scanf("%d", a + i);
        std::sort(a + 1, a + 1 + n);

        dp[0] = 1;
        for(int i = 1; i <= n; ++i){
            dp[i] = qpow(a[i], i);
            for(int j = 1; j <= i; ++j)
                dp[i] = (dp[i] - (ll)dp[j - 1] * binom(i, j - 1) % mod * qpow(a[i] - a[j], i - j + 1)) % mod;
        }

        std::printf("%d\n", (dp[n] + mod) % mod);
    }
}

来源

BZOJ3201 战斗力

评论