题目

思路

这玩意儿怎么天天考，~~问题是我还不会做！~~

重要等式 $n^m=\sum_{i=0}^{m}{n\choose i}\times i!\times S(m,i)$

其中 $S (m, i)$ 表示 $m$ 个不同的球放入 $i$ 个相同的盒子（不能空盒）的方案数。

为啥这个东西比较带劲呢？其实就是为了搞出 ${n\choose i}$ 罢了。就可以和前面的组合数互相制约。

于是原题中的式子就可以写成

$\sum_{i=0}^{n}{n\choose i}\sum_{j=0}^{k}{i\choose j}\times j!\times S(k,j)$

改变枚举顺序，就变成了

$\sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose i}{i\choose j}$

右边那个东西改写一下，得到

$\sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose j}{n-j\choose i-j}$

如果把 ${n\choose j}$ 拿出来，惊讶地发现右边就是一个 $2^{n-j}$ 罢了！于是

$ans=\sum_{j=0}^{k}j!\times S(k,j)\times{n\choose j}\times 2^{n-j}$

话说 $j!\times S(k,j)$ 也可以直接重新定义，即 $k$ 个球、 $j$ 个不同的盒子，不能空盒。

我们的枚举复杂度是 $\mathcal O(k)$ 的，不可思议！不过算 $S$ 是 $\mathcal O(k^2)$ 的递推。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long int_;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x > 9) writeint(x/10);	putchar((x%10)^48);}int qkpow(int_ b,int q,int Mod){   	int ans = 1;	for(; q; q>>=1,b=b*b%Mod)		if(q&1) ans = ans*b%Mod;	return ans;}const int Mod = 1e9+7;const int inv2 = (Mod+1)>>1;const int MaxN = 5005;int S[MaxN], inv[MaxN];int main(){   	int n = readint(), k = readint();	S[1] = 1; // 毕竟不能空盒	for(int i=2; i<=k; ++i)	for(int j=i; j>=1; --j)		S[j] = (0ll+S[j]+S[j-1])*j%Mod;	inv[1] = 1;	for(int i=2; i<=k; ++i)		inv[i] = (0ll+Mod-Mod/i)			*inv[Mod%i]%Mod;	int t = qkpow(2,n,Mod), ans = 0;	for(int i=0; i<=k; ++i){   		ans = (ans+1ll*S[i]*t)%Mod;		t = 1ll*t*inv2%Mod			*(n-i)%Mod			*inv[i+1]%Mod;	}	printf("%d\n",ans);	return 0;}

转载地址：http://ectq.baihongyu.com/

你可能感兴趣的文章

MyBatis——小知识：MyBatis_映射配置文件_参数值获取

查看>>

MyBatis——小知识：MyBatis_映射配置文件_#{}:更丰富的用法：

Hibernate的查询方式——(2)对象导航查询

查看>>