【题解】yyy loves Maths VII/Axis Walking 状压 DP luoguP2396/CF327E

观察得知，$n$ 很小，只有 $24$ ，于是欢快的做个状压 DP.

设 $f[i]$ 为使用 $i$ 集合里面的卡片能获胜的方案数，显然，我们的答案就是 $f[(n<<1)-1]$ 。但是题目说：” 大家对” 厄运数字” 的位置布置下了陷阱, 如果 yyy 停在这个格子上, 那么他就输了”。我们该怎么判断这个位置是不是陷阱呢？

所以我们再定一个 $dist$ ， $dist[i]$ 表示用 $i$ 集合里面的卡片能走到的距离，显然如果 $dist[i]$ 是厄运数字，在处理时直接跳过就好了。

否则，我们用 dist[i^(i&-i)]+dist[i&-i] 来转移 dist[i] ，想必大家都知道 i&-i 是什么意思：i 的二进制位上从右往左数第一个 1。

Code:

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int 
using namespace std;
const int MOD=1e9+7;
const int N=24;
int n,m,dist[1<<N],f[1<<N],d[2];
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}
int main(){
    IN(n);
    for(RI i=0;i<n;++i)IN(dist[1<<i]);
    IN(m);
    for(RI i=1;i<=m;++i)IN(d[i-1]);
    f[0]=1;int litm=(1<<n)-1;
    for(RI i=1;i<=litm;++i){
        int j=(i&-i);//取当前 i 的最后一位 (主要用于更新 i 的 dist 数组)
        dist[i]=dist[i^j]+dist[j];//更新 dist 数组
        if(dist[i]==d[0]||dist[i]==d[1])continue;
        //厄运数字显然不能转移，跳过
        for(RI s=i,k;s;s^=k)k=(s&-s),f[i]=(f[i]+f[i^k])%MOD; 
        //遍历 i 集合里的所有卡片，每张卡片都可以转移 f[i]。
        //注意取模！
    }printf("%d\n",f[litm]);//用完了所有卡片
    return 0;
} 

异或可以有效的消除二进制位上的数 (当然’&’ 也可以)，以达到我们遍历 $i$ 的整个二进制位的效果.