[关闭]
@ysner 2018-09-19T11:48:51.000000Z 字数 1182 阅读 2049

[CF932E]Team Work

数论


题面

解析

很显然能看出式子的现实意义:从个箱子中选出个,然后再在这个箱子中任意放入个球。
这样箱子有区别,球也有区别。

注意到小了一个级别。考虑从球的角度下手。
个球最多只能放入个箱子,除此以外就是很多空箱。
因此,我们可以枚举球总共放入多少个箱子(不允许空箱),然后其它箱子是选与不选皆可。
设当前放入个箱子,则方案数为(表示排列数)


综上,最后答案为

复杂度
注意的情况。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define db double
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int mod=1e9+7,N=5005;
  15. int n,k,S[5005][5005];
  16. ll ans;
  17. il int gi()
  18. {
  19. re int x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void Pre()
  27. {
  28. S[0][0]=1;
  29. fp(i,1,k)
  30. fp(j,1,i) S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j]%mod)%mod;
  31. }
  32. il ll ksm(re ll S,re ll n)
  33. {
  34. re ll T=S;S=1;
  35. while(n)
  36. {
  37. if(n&1) S=S*T%mod;
  38. T=T*T%mod;
  39. n>>=1;
  40. }
  41. return S;
  42. }
  43. il ll jc(re int l,re int r)
  44. {
  45. re ll res=1;
  46. fp(i,l,r) (res*=i)%=mod;
  47. return res;
  48. }
  49. int main()
  50. {
  51. n=gi();k=gi();
  52. Pre();
  53. fp(i,1,min(k,n))
  54. (ans+=1ll*S[k][i]*jc(n-i+1,n)%mod*ksm(2,n-i)%mod)%=mod;
  55. printf("%lld\n",ans);
  56. return 0;
  57. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注