题解 P2396 【yyy loves Maths VII】

· · 题解

\Large\texttt{My Blog}

题目链接：Luogu 2396

yyy 有 n 张卡片，每张卡片上都有一个数字 a_i，每次 yyy 可以选择向前走 a_i 步并丢弃第 i 张卡片。当他手上没有卡片的时候他就赢了；但是有 m 个“厄运数字”，在“厄运数字”的位置有陷阱，只要 yyy 停在这个格子上他就输了（即使终点是陷阱，那么也输了）。你需要算出 yyy 能赢的方案数，答案对 1000000007 取模。

数据范围：1\le n\le 24，0\le m\le 2

Solution

我们首先可以确定这是一道 \texttt{DP} 题目。由于并没有给出 a_i 的具体范围，因此无法把距离设计进状态；又发现每张牌只能用一次并且没有顺序限制，观察到 n 的范围也很小，我们可以考虑状压 \texttt{DP}。

我们定义 f[i] 表示使用了集合 i 内的卡片有多少种赢的方案。转移时，我们记 dis[i] 表示使用了集合 i 内的卡片到达的位置，显然当 dis[i] 为“厄运数字”时不能转移。否则我们枚举这次使用的卡片 j（j\in i），那么有转移方程：f[i]=\sum_{j=1}^n[j\in i]\cdot f[i\ \texttt{XOR}\ j]（其中 i\ \texttt{XOR}\ j 本质是从集合 i 中删去元素 j）。

时间复杂度：O(2^n\log n)

Code

#include <cstdio>

const int N=24;
const int mod=1e9+7;
int n,m,b1,b2,dis[1<<N],f[1<<N];

void upd(int &x,int y) {(x+=y)>=mod&&(x-=mod);}
void solve(int x) {
    for(int i=x,j;i;i^=j) j=i&-i,upd(f[x],f[x^j]);
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&dis[1<<i]);
    scanf("%d",&m);
    if(m>0) scanf("%d",&b1);
    if(m>1) scanf("%d",&b2);
    f[0]=1;
    int msk=(1<<n)-1;
    for(int i=1;i<=msk;++i) {
        int j=i&-i;
        dis[i]=dis[i^j]+dis[j];
        if(dis[i]==b1||dis[i]==b2) continue;
        solve(i);
    }
    printf("%d\n",f[msk]);
    return 0;
}