Codeforces 932E: Team Work

Posted by JHSN on February 23, 2018

Solutions For Codeforces 932E: Team Work



Problem

You have a team of $N$ people. For a particular task, you can pick any non-empty subset of people. The cost of having $x$ people for the task is $x^k$. Output the sum of costs over all non-empty subsets of people.

大意:给定 $n(1\leq n\leq 10^9)$ 和 $k(1\leq k \leq 5000)$,求大小为 $n$ 的集合的所有子集的子集大小的 $k$ 次幂之和,即为 $\sum_{i=0}^n\binom{n}{i}i^k$。

这个问题有很多解法,蕴含了很多数学技巧和数学知识,所以我整理了几种解法,希望能用我自己的语言记录下我对它们的理解。



Solution ①

From rkm0959

记 $(x)_n=x(x-1)(x-2)\cdots (x-n+1)$,显然当 $0\leq x\leq n$ 时,$(x)_k=0$

由二项式定理可知:

两边对 $x$ 求 $k$ 阶导可得:

令 $x=1$,则有

第二类斯特林数 Stirling numbers of the second kind:把一个大小为 $n$ 的集合划分为 $k$ 个非空集合的方案数,记为 $S(n,k)$ 或 $\left\lbrace{n\atop k}\right\rbrace$。其递推式为:

它有一个特别的性质:

所以就有

交换 $i,j$,则有

显然 $\left\lbrace{k \atop 0}\right\rbrace$=0,且当 $i > n$ 时有 $(n)_i=0$,所以有

My Code

typedef long long LL;
const LL oo = 1e9+7;
const int K=5010;
LL stir[K][K];

LL ksm(LL a, int b) { ... }
void Stirling(int n) {
	stir[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		stir[i][1] = stir[i][i] = 1;
		for (int j = 2; j < i; ++j)
			stir[i][j] = (j * stir[i - 1][j] + stir[i - 1][j - 1]) % oo;
	}
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	Stirling(k + 1);
	LL ans=0, now=ksm(2,n), inv_2=(oo+1)>>1, lim=min(n,k);
	for (int i = 0; i < lim; ++i) {
		now = now * (n - i) % oo * inv_2 % oo;
		ans = (ans + now * stir[k][i + 1]) % oo;
	}
	printf("%lld\n", ans);
	return 0;
}



Solution ②

From official solution

由二项式定理可知:

两边对 $x$ 求导,再乘上 $x$:

令 $f(a,b,c)$ 为 $x^b(1+x)^c$ 重复 $a$ 次迭代(求导并乘 $x$)后代入 $x=1$ 的结果,则答案即为 $f(k,0,n)$。因为有

所以有

其中 $f(0,b,c)=2^c$。这个过程可以利用 DP 求解,同时因为迭代不会改变最高项次数,所以有 $b+c\equiv n$,可以降一维,总状态数为 $O(k^2)$。

My Code

typedef long long LL;
const LL oo = 1e9+7;
const int K=5010;
int f[K][K], n, k;

LL ksm(LL a, int b) { ... }

int main() {
	scanf("%d%d", &n, &k);
	LL inv_2 = (oo + 1) >> 1;
	f[0][0] = ksm(2, n);
	for (int i = 1; i <= k; ++i)
		f[0][i] = inv_2 * f[0][i - 1] % oo;
	for (int i = 1; i <= k; ++i)
		for (int j = k - i; j >= 0; --j)
			f[i][j] = ((LL)f[i - 1][j] * j + (LL)f[i - 1][j + 1] * (n - j)) % oo;
	printf("%d\n", f[k][0]);
	return 0;
} 



Solution ③

From laderlappen

令 $f(a,b)=\sum_{i=0}^{n-b}\binom{n-b}{i}(i+b)^{a}$,则 $\mbox{ans}=n\cdot f(k-1,1)$,且有

所以有

其中 $f(0,b)=\sum_{i=0}^{n-b}\binom{n-b}{i}=2^{n-b}$。后续工作同 Solution ②。



Solution ④

From Jakube

$x^k$ 在组合学中可以看作在 $x$ 个人中选人选 $k$ 次的方案数,那么我们就可以换一种方法来看待这个问题:计算一个 $k$ 人的组合(其中不同的人有 $i$ 个)可以由多少个 $n$ 个人的子集生成?显然是限定这 $i$ 个人必须存在,而无所谓其它 $n-i$ 个人的情况,所以可以由 $2^{n-i}$ 个子集生成。令 $f(a,b)$ 为 $a$ 人且其中不同的人有 $b$ 个的组合数,则

如何计算 $f(a,b)$ 呢?因为 $k$ 人组合可以看成向 $k-1$ 人组合中加入一个新人或者旧人,所以有

Jakube’s Code

int MOD = 1e9 + 7;
long long dp[5001][5001];

long long power(long long b, int e) { ... }

int main() {
    int n, k;
    cin >> n >> k;
    dp[0][0] = 1;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= i; j++)
            dp[i][j] = (j * dp[i-1][j] + (n-j+1) * dp[i-1][j-1]) % MOD;
    long long r = 0;
    for (int i = 1; i <= min(k, n); i++)
        r += dp[k][i] * power(2, n-i) % MOD;
    cout << r % MOD << endl;
}



Solution ⑤

From _rqy and retrograd

显然有 $\mbox{ans}(n,0)=2^n,\mbox{ans}(n,1)=n\cdot 2^{n-1}$,猜想

即猜想答案是 $2$ 的幂次与一个 $k$ 次多项式的积(具体证明可以参考 Solution ①)。如何知道这个 $k$ 次多项式?利用 $\mbox{ans}(0,k),\mbox{ans}(1,k),…,\mbox{ans}(k,k)$ 这些样本值以及拉格朗日插值法(在处理连续整数时非常简单)求出 $ans(n,k)$,因而有

_rqy’s code

const int K = 5050;
const int mod = 1000000007;
typedef long long LL;
int n, k;
LL f[K][K], fac[K];

LL pow_mod(LL x, LL b) { ... }
inline LL inv(LL x) { return pow_mod(x, mod - 2); }

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i <= k; ++i)
		for (int j = 0; i + j <= k; ++j)
			f[i][j] = i ? (f[i - 1][j] + f[i - 1][j + 1]) % mod : pow_mod(j, k);
	if (n <= k) {
		printf("%d\n", (int)f[n][0]);
		return 0;
	}
	LL t = 1;
	for (int i = 0; i <= k; ++i) t = t * (n - i) % mod;
	fac[0] = 1;
	for (int i = 1; i <= k; ++i) fac[i] = (LL)i * fac[i - 1] % mod;
	LL ans = 0;
	for (int i = 0; i <= k; ++i) {
		LL p = f[i][0] * pow_mod(inv(2), i) % mod;
		LL num = t * inv(n - i) % mod;
		LL den = (LL)fac[i] * fac[k - i] % mod * ((k - i) & 1 ? -1 : 1);
		ans = (ans + p * num % mod * inv(den) % mod) % mod;
	}
	printf("%d\n", (int)((ans * pow_mod(2, n) % mod + mod) % mod));
	return 0;
}



评论区加载中