2024-11-24 14:30:08
发布于：云南
8阅读
0回复
0点赞
#include<bits/stdc++.h>
#define pt putchar
using namespace std;
typedef long long ll;
const int N = 21;
int n,m;
bool a[N + 1];
ll f[2][1 << N | 7][N + 1];
int main(){
freopen("festival.in","r",stdin);
freopen("festival.out","w",stdout);
cin >> n >> m;
for(int i=1;i<=m;i++){
int t; cin >> t;
a[t] = 1;
}
f[1][1][a[1]] = 1;
for(int i=2;i<=n;i++){
for(int S=0;S<(1<<i);S++){
int v=__builtin_popcount(S);
if(v>m)continue;
for(int p=0;p<=i;p++)f[i&1][S][p]=0;
}
for(int S=0;S<(1<<(i-1));S++){
int v=__builtin_popcount(S);
if(v>m||v+n-i+1<m)continue;
int hbit=0;while((1<<(hbit))<=S)hbit++;
for(int j=1;j<=i;j++){
int T=0;
if(j>hbit){
T=S|(1<<(j-1));
}
else{
int D=j==0?0:(S&((1<<(j-1))-1)),O=S^D;
T=D|((O-(O&(-O)))<<1)|(1<<(j-1));
}
ll *h=&f[i&1][T][0],*g=&f[(i-1)&1][S][0];
if(a[i]){
for(int p=0;p<j;p++)h[j]+=g[p];
}
else{
for(int p=0;p<j;p++)h[p]+=g[p];
for(int p=j;p<i;p++)h[p+1]+=g[p];
}
}
}
}
ll ans = 0;
for(int S = 0;S < (1 << n);S++){
if(__builtin_popcount(S) == m){
for(int p = 1;p <= n;p++) ans += f[n & 1][S][p];
}
}
cout << ans;
return 0;
}
这里空空如也
有帮助，赞一个