Iahub wants to meet his girlfriend Iahubina. They both live in Ox axis (the horizontal axis). Iahub lives at point 0 and Iahubina at point d.
Iahub has n positive integers _a_1, _a_2, ..., a__n. The sum of those numbers is d. Suppose _p_1, _p_2, ..., p__n is a permutation of {1, 2, ..., n}. Then, let _b_1 = _a__p_1, _b_2 = _a__p_2and so on. The array b is called a "route". There are n! different routes, one for each permutation p.
Iahub's travel schedule is: he walks _b_1 steps on Ox axis, then he makes a break in point _b_1. Then, he walks _b_2 more steps on Ox axis and makes a break in point _b_1 + _b_2. Similarly, at j-th (1 ≤ j ≤ n) time he walks b__j more steps on Ox axis and makes a break in point _b_1 + _b_2 + ... + b__j.
Iahub is very superstitious and has k integers which give him bad luck. He calls a route "good" if he never makes a break in a point corresponding to one of those _k_numbers. For his own curiosity, answer how many good routes he can make, modulo 1000000007 (109 + 7).
Input
The first line contains an integer n (1 ≤ n ≤ 24). The following line contains _n_integers: _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).
The third line contains integer k (0 ≤ k ≤ 2). The fourth line contains k positive integers, representing the numbers that give Iahub bad luck. Each of these numbers does not exceed 109.
题意：给出n个数，给出至多两个数k1，k2，求这n个数每个排列中前缀和不含k1/k2的排列个数
题解：首先看着范围考虑状压dp
dp[sta]=sigma(dp[sta^1<<i]) i为sta中所有1的位置
sum[sta]==k1||sum[sta]==k2 dp[sta]=0;
然后显然直接模会非常慢， 所以用-mod代替模
代码如下：
1#pragma GCC optimize(3) 2#include<cstdio> 3#include<cstring> 4#include<iostream> 5#include<algorithm> 6#define mod 1000000007 7using namespace std; 8 9long long n,dp[1<<24],sum[1<<24],kkk[2],k; 10 11inline int lowbit(int x) 12{ 13 return x&-x; 14} 15 16int main() 17{ 18 scanf("%lld",&n); 19 int tmp; 20 for(int i=0;i<n;i++) 21 { 22 scanf("%d",&tmp); 23 sum[1<<i]=tmp; 24 } 25 scanf("%lld",&k); 26 for(int i=0;i<k;i++) 27 { 28 scanf("%lld",&kkk[i]); 29 } 30 dp[0]=1; 31 for(int i=1;i<(1<<n);i++) 32 { 33 sum[i]=sum[i^lowbit(i)]+sum[lowbit(i)]; 34 if(sum[i]==kkk[1]||sum[i]==kkk[0]) 35 { 36 continue; 37 } 38 for(int j=i;j;j-=lowbit(j)) 39 { 40 dp[i]=dp[i]+dp[i^lowbit(j)]; 41 if(dp[i]>=mod) dp[i]-=mod; 42 } 43 } 44 printf("%lld\n",dp[(1<<n)-1]); 45}