【题解】Team Work 第二类 stirling 数 CF923F ——quhengyi11

喵

题意

求
$$\sum_{i=1}^n C_n^i i^k$$

题解

第二类 $stirling$数模板题没错了

根据套路化简

$$\sum_{i=1}^n C_n^i \sum_{j=1}^k A_i^jS_k^j$$

交换枚举顺序

$$\sum_{j=1}^k S_k^j j!\sum_{i=1}^n C_n^i C_i^j$$

显然从 $n$个里面选 $i$个再从 $i$个里面选 $j$个等价于从 $n$个里面选 $j$个然后再判断 $i$的方案数

即 $\sum_{i=1}^nC_n^i C_i^j=C_n^j\times 2^{n-j}$

然后答案就是

$$\sum_{j=1}^k S_k^j j!C_n^j\times 2^{n-j}$$

总结：第二类 $stirling$数的难点就是交换枚举顺序后通过组合意义化简式子，需要冷静想 $qwq$

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define mod 1000000007
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 5005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int n, m, K;
struct edge {
    int nxt, v;
} e[N << 1];
int head[N], tot, k;
inline void addedge (int u, int v)
{
    e[++tot] = (edge) { head[u], v };
    head[u] = tot;
}
ll s[N][N], fac[N], ans;
inline ll pow (ll x, int y)
{
    ll ret = 1;
    if (y < 0) return 0;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
int main ()
{
    read(n); read(k);
    s[0][0] = 1; fac[0] = 1;
    fo (i, 1, k)
    {
        fac[i] = fac[i - 1] * i % mod;
        fo (j, 1, i)
            s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j) % mod;
    }
    ll now = n;
    fo (i, 1, k)
    {
        (ans += s[k][i] * pow(2, n - i) % mod * now % mod) %= mod;
        now = now * (n - i) % mod;
    }
    printf("%lld", ans);
    return 0;
}