CF 961G Partitions

推不动式子

我们考虑每一个$w_i$对答案的贡献，因为题目中定义集合的价值为$W(S) = \left | S \right |\sum_{x \in S}w_x$，这个系数$\left | S \right |$可以看作集合中所有的元素（包括$i$自己）对$i$产生了一次贡献，那么我们考虑一个元素$j$对$i$的贡献：

1、$j == i$的时候，相当于求把$n$个小球放到$k$个盒子里面的方案数，为$S(n, k)$（$S$表示第二类斯特林数）。

2、$j \neq i$的时候，只有$j$和$i$放在同一个集合里面才能产生贡献，为$S(n - 1, k)$。

然后代入第二类斯特林数的通项公式直接算就好了。

最后的答案就是

$$(S(n, k) + (n - 1)S(n - 1, k)) * \sum_{i = 1}^{n}w_i$$

时间复杂度$O(klogk)$。

另外一种高能的推法：传送门

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 2e5 + ;

const ll P = 1e9 + ;

ll sum = , fac[N], inv[N];

inline ll fpow(ll x, ll y) {

    ll res = 1LL;

    for (; y > ; y >>= ) {

        if (y & ) res = res * x % P;

        x = x * x % P;

    }

    return res;

}

inline ll getS(int n, int k) {

    ll res = ;

    for (int i = ; i <= k; i++) {

        ll opt = i &  ? -1LL : 1LL;

        res = (res + opt * inv[i] % P * fpow(k - i, n) % P * inv[k - i] % P + P) % P;

    }

    return res;

}

int main() {

    int n, k;

    scanf("%d%d", &n, &k);

    for (int i = ; i <= n; i++) {

        ll now; scanf("%lld", &now);

        sum = (sum + now) % P;

    }

    fac[] = ;

    for (int i = ; i <= n; i++) fac[i] = fac[i - ] * i % P;

    inv[n] = fpow(fac[n], P - );

    for (int i = n - ; i >= ; i--) inv[i] = inv[i + ] * (i + ) % P;

    ll ans = (getS(n, k) + (n - ) * getS(n - , k) % P) % P;

    ans = ans * sum % P;

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

    return ;

}

巴特西

CF 961G Partitions

最新文章

热门文章