Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <ctime>
- #include <deque>
- #include <functional>
- #include <iomanip>
- #include <iostream>
- #include <list>
- #include <map>
- #include <numeric>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <utility>
- #include <vector>
- #include <cstring>
- #define mod 1000000007
- #define maxn 30
- #define maxf 1000000
- #define maxk 5
- using namespace std;
- int n,K;
- int a[maxn];
- int hole[maxk];
- map< pair<int,int>,int > ID;
- int IDcnt = 0;
- map< pair<int,int>,int > cnt[maxf];
- long long perm[maxn],ans = 0;
- int PX,PY;
- bool mark[maxn];
- int getID(int alpha,int beta) {
- pair<int,int> D = make_pair(alpha,beta);
- if (!ID.count(D)) ID[D] = IDcnt++;
- return ID[D];
- }
- inline void generate(int low,int high,int pos,int n1,int s1,int n2,int s2) {
- if (pos > high) {
- int idx = getID(s1,s2);
- cnt[idx][make_pair(n1,n2)]++;
- return;
- }
- generate(low,high,pos + 1,n1 + 1,s1 + a[pos],n2,s2);
- generate(low,high,pos + 1,n1,s1,n2 + 1,s2 + a[pos]);
- generate(low,high,pos + 1,n1,s1,n2,s2);
- }
- inline void recurse(int low,int high,int pos,int n1,int s1,int n2,int s2) {
- if (pos > high) {
- if (!ID.count(make_pair(PX - s1,PY - s2))) return;
- int idx = ID[make_pair(PX - s1,PY - s2)];
- for (map< pair<int,int>,int >::iterator it = cnt[idx].begin(); it != cnt[idx].end(); it++) {
- int l1 = it->first.first,l2 = it->first.second,val = it->second;
- long long prod = (perm[l1 + n1] * perm[l2 + n2]) % mod;
- prod = (prod * perm[n - (l1 + n1) - (l2 + n2)]) % mod;
- ans = (ans + prod * val) % mod;
- }
- return;
- }
- if (s1 + a[pos] <= PX) recurse(low,high,pos + 1,n1 + 1,s1 + a[pos],n2,s2);
- if (s2 + a[pos] <= PY) recurse(low,high,pos + 1,n1,s1,n2 + 1,s2 + a[pos]);
- recurse(low,high,pos + 1,n1,s1,n2,s2);
- }
- long long compute(int X,int Y) {
- PX = X; PY = Y;
- ans = 0;
- recurse(n/2,n - 1,n/2,0,0,0,0);
- return ans;
- }
- void backtrack(int pos,long long sum) {
- if (pos >= n) {
- ans++;
- return;
- }
- for (int i = 0; i < n; i++) if (!mark[i]) {
- bool flag = true;
- for (int j = 0; j < K; j++) if (sum + a[i] == hole[j]) flag = false;
- if (!flag) continue;
- mark[i] = true;
- backtrack(pos + 1,sum + a[i]);
- mark[i] = false;
- }
- }
- int main() {
- cin >> n;
- perm[0] = 1;
- for (int i = 1; i <= n; i++) perm[i] = (perm[i - 1] * i) % mod;
- for (int i = 0; i < n; i++) cin >> a[i];
- cin >> K;
- for (int i = 0; i < K; i++) cin >> hole[i];
- sort(hole,hole + K);
- if (n <= 10) {
- ans = 0;
- backtrack(0,0);
- cout << ans << endl;
- return 0;
- }
- generate(0,n/2 - 1,0,0,0,0,0);
- long long ret = perm[n];
- if (K > 0) {
- ret -= compute(hole[0],0);
- if (K > 1) ret -= compute(hole[1],0);
- }
- if (K > 1) ret += compute(hole[0],hole[1] - hole[0]);
- ret %= mod;
- if (ret < 0) ret += mod;
- cout << ret << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement