题解 CF327E 【Axis Walking】
可爱即是正义
2018-08-04 15:26:41
### 谨以此篇题解来纪念的我可怜的状压水平.....
## 题目大意:给一个序列,可以任意重排,但是前缀和不能出现给定数字中的数,问有几种排列方式
注意到N很小...~~K更小~~所以应该是可以状压~~因为暴力全排列过不去~~
一般全排列只能到n==11,由于状压加上lowbit可以跑得很快...因为我太弱跑的仍然很慢
所以说用一个sum数组记录所选的数得前缀和,所选的数在sum的下标中体现
下标的每一个二进制位代表一个数选还是不选。
具体求可以直接枚举,二进制暴力的上界是n==15,而本题n到了24,所以考虑优化
考虑枚举到在当前这位之前,可能有很多位0
所以很自然的想到lowbit
------------
lowbit的意义:~~你大概翻译一下也能猜出来,~~就是求一个二进制数从右向左数第一个1的位权
#### 举个栗子:28的二进制表示为 11100
所以lowbit(28)为8
具体求法不再赘述
------------
回到本题,有了lowbit这个东西便能提高程序效率
先上我的擦边代码,具体用法在代码里注释出来
```cpp
#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;
const int M=(1<<24)+10;
const int mod=1e9+7;
typedef long long ll;
int a[M];
int o[M];
ll f[M];
ll sum[M];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d",&a[i]);
sum[1<<i]=a[i];//每一位代表一个a[i]
}
int k;scanf("%d",&k);
for(int i=1;i<=k;++i)scanf("%d",&o[i]);
f[0]=1;
int lim=1<<n;//最多有n位,所以最大的下标不会超过(2^n)-1
lim--;
for(int i=1;i<=lim;++i)
{
sum[i]=sum[i&~lowbit(i)]+sum[lowbit(i)];
if(sum[i]==o[1]||sum[i]==o[2])continue;//k只有2,特判即可
for(int j=i;j;j-=lowbit(j))//快速访问每一个为1的位
{
f[i]+=f[i&~lowbit(j)];
if(f[i]>mod)f[i]-=mod;//玄学,long long的取模非常慢 --Scαpe
}
}
return !printf("%lld\n",f[lim]);//皮一手
}
```
这里补充一下~这个逻辑运算符,它的作用是把一个二进制数每一位取反
即每一位的0变成1,1变成0
所以i&~lowbit(i)的意义为去掉一个二进制数的lowbit后的值
--end
原文借鉴了[呐](https://blog.csdn.net/Tc_To_Top/article/details/47162427)中的思想,加上我自己本人的一些见解组合而成,不喜勿喷