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, a, ..., a. The sum of those numbers is d. Suppose p, p, ..., p is a permutation of {1, 2, ..., n}. Then, let b = a, b = aand 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 steps on Ox axis, then he makes a break in point b. Then, he walks b more steps on Ox axis and makes a break in point b + b. Similarly, at j-th (1 ≤ j ≤ n) time he walks b more steps on Ox axis and makes a break in point b + b + ... + b.
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 knumbers. For his own curiosity, answer how many good routes he can make, modulo 1000000007 (10 + 7).
Input
The first line contains an integer n (1 ≤ n ≤ 24). The following line contains nintegers: a, a, ..., a (1 ≤ a ≤ 10).
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 10.
题意：给出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代替模
代码如下：
#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std; long long n,dp[<<],sum[<<],kkk[],k; inline int lowbit(int x)
{
return x&-x;
} int main()
{
scanf("%lld",&n);
int tmp;
for(int i=;i<n;i++)
{
scanf("%d",&tmp);
sum[<<i]=tmp;
}
scanf("%lld",&k);
for(int i=;i<k;i++)
{
scanf("%lld",&kkk[i]);
}
dp[]=;
for(int i=;i<(<<n);i++)
{
sum[i]=sum[i^lowbit(i)]+sum[lowbit(i)];
if(sum[i]==kkk[]||sum[i]==kkk[])
{
continue;
}
for(int j=i;j;j-=lowbit(j))
{
dp[i]=dp[i]+dp[i^lowbit(j)];
if(dp[i]>=mod) dp[i]-=mod;
}
}
printf("%lld\n",dp[(<<n)-]);
}