题目分析:
容易想到若集合$S$为前缀时,$S$外的所有元素的排列的前缀是小于$0$的,DP可以做到,令排列前缀个数小于0的是g[S].
令f[S]表示$S$是前缀,转移可以通过在前面插入元素完成。
代码:
#include<bits/stdc++.h>
using namespace std; const int maxn = ; const int mod = ; int n;
int a[maxn];
int f[<<],g[<<],sum[<<],arr[<<]; void read(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
} void dfs(int now){
if(f[now]) return;
for(int i=;i<n;i++){
if((<<i)&now){
if(f[now-(<<i)]) sum[now] = sum[now-(<<i)]+a[i+];
else dfs(now-(<<i)),sum[now] = sum[now-(<<i)]+a[i+];
f[now] = ; break;
}
}
} int dfs2(int now){
if(arr[now]) return f[now];
arr[now] = ;
for(int i=;i<=n;i++){
if((<<i-)&now){
int z = dfs2(now-(<<i-));
if(sum[now-(<<i-)] >= ) f[now] += z,f[now] %= mod;
}
}
return f[now];
} int dfs3(int now){
if(arr[now]) return g[now];
arr[now] = ;
for(int i=;i<=n;i++){
if((<<i-)&now){
int z = dfs3(now-(<<i-));
if(sum[now] < ) g[now] += z,g[now]%=mod;
}
}
return g[now];
} void work(){
f[] = ;for(int i=;i<(<<n);i++) dfs(i);
memset(f,,sizeof(f));
arr[] = ; f[] = ;
dfs2((<<n)-);
memset(arr,,sizeof(arr));
arr[] = ; g[] = ;
dfs3((<<n)-);
int res = ;
for(int i=;i<(<<n);i++){
res += (1ll*sum[i]*((1ll*f[i]*g[(<<n)--i])%mod))%mod;
res %= mod;
}
res += mod; res %= mod;
printf("%d",res);
} int main(){
read();
work();
return ;
}