fork download
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. using namespace std;
  5. typedef long long int ll;
  6. const int mod = 1000000007;
  7. int ncr[1002002],sweets,inv_ncr[1002002];
  8. int input[1002][2002];
  9. int use[1002],x,answer[2002],copy[2002],bine[2002];
  10. void constant()
  11. {
  12. memset(inv_ncr,0,sizeof(inv_ncr));
  13. ncr[0]=inv_ncr[0]=1;
  14. inv_ncr[0] = inv_ncr[1] = 1;
  15. for(int i = 2; i <= 1002000; i++)
  16. inv_ncr[i] = (-(ll)(mod/i) * (ll)inv_ncr[mod % i]) % mod + mod;
  17.  
  18. for(int i=1;i<=1002000;i++){
  19. ncr[i]=((ll)ncr[i-1]*(ll)i)%mod;
  20. inv_ncr[i]=((ll)inv_ncr[i]*(ll)inv_ncr[i-1])%mod;
  21. }
  22. }
  23. int compute(int n,int r)
  24. {
  25. if(n<r) return 0;
  26. if(r==0 || n==r) return 1;
  27. return ( (ll) ( ((ll)ncr[n]*(ll)inv_ncr[r])%mod ) * (ll)inv_ncr[n-r] )%mod;
  28. }
  29. void multiply(int mul)
  30. {
  31. for(int i=0;i<=sweets;i++) copy[i]=answer[i];
  32. memset(answer,0,sizeof(answer));
  33. for(int i=0;i<=sweets;i+=mul){ //copy
  34. for(int j=0;j<=sweets-i;j++){ //input[mul]
  35. answer[i+j]=((ll)answer[i+j]+(ll)copy[j]*(ll)input[mul][i])%mod;
  36. }
  37. }
  38. }
  39. void print(int Array[])
  40. {
  41. for(int i=0;i<20;i++) printf("%d ",Array[i]);
  42. printf("\n");
  43. }
  44. void solve()
  45. {
  46. int p,s,prt=0,req,n,Q;
  47. scanf("%d",&n);
  48. memset(use,0,sizeof(use));
  49. x=1;
  50. for(int i=0;i<n;i++){
  51. scanf("%d",&x);
  52. if(x>0)
  53. use[x+1]++;
  54. }
  55. sweets=2000;
  56. memset(answer,0,sizeof(answer));
  57. answer[0]=1;
  58. for(int i=2;i<=1001;i++){
  59. p=use[i];
  60. if(p>0)
  61. for(int j=0;j<=sweets;j+=i){
  62. s=j/i;
  63. input[i][j]= compute(p,s);
  64. if(s&1)
  65. input[i][j]=mod-input[i][j];
  66.  
  67. }
  68. }
  69. for(int i=2;i<=1001;i++){
  70. if(use[i]){
  71. multiply(i);
  72. }
  73. }
  74. for(int i=0;i<2001;i++)
  75. bine[i]=compute(n+i-1,i);
  76. memset(copy,0,sizeof(copy));
  77. for(int i=0;i<=2000;i++){
  78. for(int j=0;j<=2000-i;j++){
  79. copy[i+j]=((ll)copy[i+j]+(ll)answer[i]*(ll)bine[j])%mod;
  80. }
  81. }
  82. scanf("%d",&Q);
  83. while(Q--){
  84. scanf("%d",&x);
  85. printf("%d\n",copy[x]);
  86. }
  87. }
  88. int main()
  89. {
  90. int test;
  91. constant();
  92. //return 0;
  93. test=1;
  94. while(test--) solve();
  95. return 0;
  96. }
  97.  
Time limit exceeded #stdin #stdout 5s 18984KB
stdin
Standard input is empty
stdout
Standard output is empty