「Luogu 2396」yyy loves Maths VII

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%