题解 CF327E 【Axis Walking】

Solution [CF327E] Axis Walking

题目大意:给定一个数列,求有多少种排列方式使得这个数列的任意前缀和不会成为(k)个数中的任意一个

动态规划,计数,(lowbit)优化(dp)

分析:看到数据范围(n leq 24)就马上可以意识到这题要么是状压(dp),要么是搜索.可是搜索全排列复杂度高达(24!),而且如果出题人卡你(请意识到这是(CF)的题目),你的剪枝是没有任何软用的.

比如这组数据:

24
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
2333 2333

你搜索很不好搞啊,那么我们就只能使用状压(dp)了.既然都上状压(dp)了,状态也就不难定义了吧:

我们用(f[S])来表示选择集合(S)中的数的排列方案总数,最终答案为(f[U]),(U)为全集.

蒟蒻先给出代码,再看具体为何

#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 24;
long long f[1 << maxn],sum[1 << maxn],val[maxn],no[3],n,k;//f由上文易知,sum[x]表示集合x内元素之和,no就是给定的k个元素,val为原数列
inline int lowbit(int x){
    return x & (-x);
}
int main(){
#ifdef LOCAL
    freopen("fafa.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i = 0;i < n;i++)//读入
        scanf("%d",&val[i]),sum[1 << i] = val[i];//初始化sum数组,很eazy
    scanf("%d",&k);
    for(int i = 0;i < k;i++)
        scanf("%d",&no[i]);
    for(int i = 0;i < n;i++)//dp边界
        f[1 << i] = (val[i] != no[0] && val[i] != no[1]) ? 1 : 0;
    for(int i = 1;i < (1 << n);i++){//进行dp
        sum[i] = sum[i ^ lowbit(i)] + sum[lowbit(i)];
        if(sum[i] == no[0] || sum[i] == no[1])continue;
        for(int j = i;j;j -= lowbit(j)){//枚举集合i的每一个二进制1
            f[i] += f[i ^ lowbit(j)];
            if(f[i] >= mod)f[i] -= mod;//据说可以加速long long取余
        }
    }
    printf("%lld
",f[(1 << n) - 1]);//输出
    return 0;
}

先看(sum)数组,(sum[x])表示集合(x)的和,这个很容易理解.因为(i ; xor lowbit(i))和(lowbit(i))都是(i)的真子集,所以计算集合(i)时它们都算过了

再看(f)数组,边界很容易理解?只有一个数,并且这个数满足限制那方案数肯定为(1)

最不好理解的应该就是转移了吧(蒟蒻当初在这里卡了很久).程序描述的其实是酱紫一个方程:

(f[S] = sum f[x]),其中集合(x)为集合(S)去掉一个元素后得来的

这样应该就很明了了吧?可是为什么是对的呢?

对于一个集合(f[x]),你可以将去掉的那个元素加在每一个合法方案的最末尾,因为(sum)满足限制条件,所以(f[x])的合法方案任然是合法方案,因此加入我们枚举的元素后(f[x])的值不会有变动,所以转移方程是正确的