题解归档 - cf932E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932E
• 本地来源：problems/cf932E/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/E
• 原始标题：CF932E Team Work

思路

CF932E Team Work

题意

N 个人，选任意非空子集，大小为 x 的子集代价为 x^k。求所有非空子集代价之和，模 1e9+7。

做法

答案为

[
\sum_{x=1}^{N} \binom{N}{x} x^k
]

用第二类 Stirling 数展开 x^k：

[
x^k = \sum_{j=0}^{k} S(k,j)\, x^{\underline{j}}
]

其中 x^{\underline{j}} = x(x-1)\cdots(x-j+1) 为下降阶乘。

关键恒等式：

[
\sum_{x=j}^{N} \binom{N}{x} x^{\underline{j}} = (N)_j \cdot 2^{N-j}
]

于是

[
\text{ans} = \sum_{j=0}^{k} S(k,j)\,(N)_j\,2^{N-j}
]

• S(k,j) 用 O(k^2) DP 预处理（k ≤ 5000）
• (N)_j 逐项乘 (N-j+1) mod MOD
• 2^{N-j} 维护当前幂，每步乘 inv2

复杂度

O(k^2) 时间，O(k^2) 空间。

验证

样例 N=3,k=2 → 24；N=1,k=1 → 1。与暴力枚举 2^N 子集一致。

代码

来源：problems/cf932E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:25:45
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxk=5005,mod=1e9+7,inv2=500000004;
ll cur[maxk],pre[maxk];
ll ksm(ll a,ll b){
    ll zc=1;
    a%=mod;
    while(b){
        if(b&1) zc=zc*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return zc;
}
int main(){
    ll n,k,i,j,ans,f,pw;
    cin>>n>>k;
    pre[0]=1;
    for(i=1;i<=k;i++){
        cur[0]=0;
        for(j=1;j<=i;j++) cur[j]=(pre[j-1]+pre[j]*j)%mod;
        for(j=0;j<=i;j++) pre[j]=cur[j];
    }
    ans=0;
    f=1;
    pw=ksm(2,n);
    for(j=0;j<=k;j++){
        ans=(ans+pre[j]*f%mod*pw)%mod;
        f=f*((n-j)%mod)%mod;
        pw=pw*inv2%mod;
    }
    cout<<ans<<"\n";
    return 0;
}