fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/s2G8US
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!