本文共 2211 字，大约阅读时间需要 7 分钟。
题目
思路
这玩意儿怎么天天考，问题是我还不会做！
重要等式 n m = ∑ i = 0 m ( n i ) × i ! × S ( m , i ) n^m=\sum_{i=0}^{m}{n\choose i}\times i!\times S(m,i) nm=i=0∑m(in)×i!×S(m,i)
其中 S ( m , i ) S(m,i) S(m,i) 表示 m m m 个不同的球放入 i i i 个相同的盒子（不能空盒）的方案数。
为啥这个东西比较带劲呢？其实就是为了搞出 ( n i ) {n\choose i} (in) 罢了。就可以和前面的组合数互相制约。
于是原题中的式子就可以写成
∑ i = 0 n ( n i ) ∑ j = 0 k ( i j ) × j ! × S ( k , j ) \sum_{i=0}^{n}{n\choose i}\sum_{j=0}^{k}{i\choose j}\times j!\times S(k,j) i=0∑n(in)j=0∑k(ji)×j!×S(k,j)
改变枚举顺序，就变成了
∑ j = 0 k j ! × S ( k , j ) ∑ i = 0 n ( n i ) ( i j ) \sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose i}{i\choose j} j=0∑kj!×S(k,j)i=0∑n(in)(ji)
右边那个东西改写一下，得到
∑ j = 0 k j ! × S ( k , j ) ∑ i = 0 n ( n j ) ( n − j i − j ) \sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose j}{n-j\choose i-j} j=0∑kj!×S(k,j)i=0∑n(jn)(i−jn−j)
如果把 ( n j ) {n\choose j} (jn) 拿出来，惊讶地发现右边就是一个 2 n − j 2^{n-j} 2n−j 罢了！于是
a n s = ∑ j = 0 k j ! × S ( k , j ) × ( n j ) × 2 n − j ans=\sum_{j=0}^{k}j!\times S(k,j)\times{n\choose j}\times 2^{n-j} ans=j=0∑kj!×S(k,j)×(jn)×2n−j
话说 j ! × S ( k , j ) j!\times S(k,j) j!×S(k,j) 也可以直接重新定义，即 k k k 个球、 j j j 个不同的盒子，不能空盒。
我们的枚举复杂度是 O ( k ) \mathcal O(k) O(k) 的，不可思议！不过算 S S S 是 O ( k 2 ) \mathcal O(k^2) O(k2) 的递推。
代码
#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;}
发表评论
最新留言
关于作者
