题解 CF327E 【Axis Walking】

可爱即是正义

2018-08-04 15:26:41

Solution

### 谨以此篇题解来纪念的我可怜的状压水平..... ## 题目大意:给一个序列,可以任意重排,但是前缀和不能出现给定数字中的数,问有几种排列方式 注意到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)中的思想,加上我自己本人的一些见解组合而成,不喜勿喷