Guest User

Untitled

a guest
Jul 4th, 2013
316
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <ctime>
  7. #include <deque>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <numeric>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <utility>
  19. #include <vector>
  20. #include <cstring>
  21. #define mod 1000000007
  22. #define maxn 30
  23. #define maxf 1000000
  24. #define maxk 5
  25. using namespace std;
  26.  
  27. int n,K;
  28. int a[maxn];
  29. int hole[maxk];
  30. map< pair<int,int>,int > ID;
  31. int IDcnt = 0;
  32. map< pair<int,int>,int > cnt[maxf];
  33. long long perm[maxn],ans = 0;
  34. int PX,PY;
  35. bool mark[maxn];
  36.  
  37. int getID(int alpha,int beta) {
  38. pair<int,int> D = make_pair(alpha,beta);
  39. if (!ID.count(D)) ID[D] = IDcnt++;
  40. return ID[D];
  41. }
  42.  
  43. inline void generate(int low,int high,int pos,int n1,int s1,int n2,int s2) {
  44. if (pos > high) {
  45. int idx = getID(s1,s2);
  46. cnt[idx][make_pair(n1,n2)]++;
  47. return;
  48. }
  49. generate(low,high,pos + 1,n1 + 1,s1 + a[pos],n2,s2);
  50. generate(low,high,pos + 1,n1,s1,n2 + 1,s2 + a[pos]);
  51. generate(low,high,pos + 1,n1,s1,n2,s2);
  52. }
  53.  
  54. inline void recurse(int low,int high,int pos,int n1,int s1,int n2,int s2) {
  55. if (pos > high) {
  56. if (!ID.count(make_pair(PX - s1,PY - s2))) return;
  57. int idx = ID[make_pair(PX - s1,PY - s2)];
  58. for (map< pair<int,int>,int >::iterator it = cnt[idx].begin(); it != cnt[idx].end(); it++) {
  59. int l1 = it->first.first,l2 = it->first.second,val = it->second;
  60. long long prod = (perm[l1 + n1] * perm[l2 + n2]) % mod;
  61. prod = (prod * perm[n - (l1 + n1) - (l2 + n2)]) % mod;
  62. ans = (ans + prod * val) % mod;
  63. }
  64. return;
  65. }
  66. if (s1 + a[pos] <= PX) recurse(low,high,pos + 1,n1 + 1,s1 + a[pos],n2,s2);
  67. if (s2 + a[pos] <= PY) recurse(low,high,pos + 1,n1,s1,n2 + 1,s2 + a[pos]);
  68. recurse(low,high,pos + 1,n1,s1,n2,s2);
  69. }
  70.  
  71. long long compute(int X,int Y) {
  72. PX = X; PY = Y;
  73. ans = 0;
  74. recurse(n/2,n - 1,n/2,0,0,0,0);
  75. return ans;
  76. }
  77.  
  78. void backtrack(int pos,long long sum) {
  79. if (pos >= n) {
  80. ans++;
  81. return;
  82. }
  83. for (int i = 0; i < n; i++) if (!mark[i]) {
  84. bool flag = true;
  85. for (int j = 0; j < K; j++) if (sum + a[i] == hole[j]) flag = false;
  86. if (!flag) continue;
  87. mark[i] = true;
  88. backtrack(pos + 1,sum + a[i]);
  89. mark[i] = false;
  90. }
  91. }
  92.  
  93. int main() {
  94. cin >> n;
  95. perm[0] = 1;
  96. for (int i = 1; i <= n; i++) perm[i] = (perm[i - 1] * i) % mod;
  97. for (int i = 0; i < n; i++) cin >> a[i];
  98. cin >> K;
  99. for (int i = 0; i < K; i++) cin >> hole[i];
  100. sort(hole,hole + K);
  101. if (n <= 10) {
  102. ans = 0;
  103. backtrack(0,0);
  104. cout << ans << endl;
  105. return 0;
  106. }
  107.  
  108. generate(0,n/2 - 1,0,0,0,0,0);
  109. long long ret = perm[n];
  110. if (K > 0) {
  111. ret -= compute(hole[0],0);
  112. if (K > 1) ret -= compute(hole[1],0);
  113. }
  114. if (K > 1) ret += compute(hole[0],hole[1] - hole[0]);
  115. ret %= mod;
  116. if (ret < 0) ret += mod;
  117. cout << ret << endl;
  118. }
RAW Paste Data