「Luogu 2396」yyy loves Maths VII

发表于 | | 阅读次数:
字数统计: 516 字

Description

题目链接：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

我们首先可以确定这是一道 $\text{DP}$ 题目。由于并没有给出 $a_i$ 的具体范围，因此无法把距离设计进状态；又发现每张牌只能用一次并且没有顺序限制，观察到 $n$ 的范围也很小，我们可以考虑状压 $\text{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\ \text{XOR}\ j]$（其中 $i\ \text{XOR}\ j$ 本质是从集合 $i$ 中删去元素 $j$）。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#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;
}
0%