正題

題目鏈接:https://www.luogu.com.cn/problem/CF932E

---

題目大意

給出$n,k$，求$$\sum _{i=1}^{n}C(n,i)?i^k$$

---

解題思路

上式子的話，大體是先拆開$i^k$變成$$\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)\sum _{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}\left(\genfrac{}{}{0ex}{}{i}{j}\right)j!$$
$$?\sum _{i=1}^n\sum _{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}\left(\genfrac{}{}{0ex}{}{i}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{i}\right)j!$$
拆開$C$然后化解一下
$$?\sum _{i=1}^n\sum _{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}?\frac{1}{(i?j)!}?\frac{n!}{(n?i)!}$$
$$?\sum _{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}\frac{n!}{(n?j)!}\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n?j}{n?i}\right)$$
$$\sum _{j=1}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}P(n,j)?2^{n?j}$$

理解一下的話就是最開的式子的意義是：在$n$種顏色中選擇若干種然后再去涂$k$個(gè)物品，求方案種數(shù)。轉(zhuǎn)換一下的話我們可以把$k$個(gè)物品分成若干個(gè)集合，每個(gè)物品集合顏色相同，然后再$n$個(gè)顏色中排列出這些顏色，剩下的都是可選可不選的。

然后遞推處理第二類斯特林?jǐn)?shù)就好了，時(shí)間復(fù)雜度$O(k^2)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5100,XJQ=1e9+7; ll n,k,S[N][N],ans; ll power(ll x,ll b){ll ans=1;if(b<0)return power(power(x,-b),XJQ-2);while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } ll P(ll n,ll m){ll tmp=1;if(n<m)return 0;for(ll i=n-m+1;i<=n;i++)tmp=tmp*i%XJQ;return tmp; } int main() {scanf("%lld%lld",&n,&k);S[0][0]=1;for(ll i=1;i<=k;i++)for(ll j=1;j<=i;j++)S[i][j]=(S[i-1][j-1]+j*S[i-1][j]%XJQ)%XJQ;for(ll i=0;i<=k;i++)(ans+=S[k][i]*P(n,i)%XJQ*power(2,n-i)%XJQ)%=XJQ;if(!k)ans--;printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF932E-Team Work【斯特林数,组合数学】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。