目录
显示
题目链接
https://www.luogu.com.cn/problem/P2396
题解
数据范围并不大,我们考虑用状压DP的方法解决本题。
定义状态 \(f_i\) 代表使用集合 \(i\) 中的卡片完成游戏的方案数,\(dist_i\) 表示使用集合 \(i\) 中的卡片走到的位置。
我们在进行状态转移的时候,枚举这一次要用的卡片 \(j\),则:
$$f_i= \sum_{j \in i} f_j$$
别忘了跳过厄运数字。(\(dist\) 就是来做这个判断的)
然而本题数据范围卡的很紧,懒得加太多常数优化怎么办,那就吸氧吧233
#include <cstdio> #include <algorithm> #define MOD 1000000007 using namespace std; int f[17000005],dist[17000005]; int b1,b2; inline int lowbit(int x) { return x&(-x); } int main() { int n,m; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&dist[1<<i]); scanf("%d",&m); if(m==1)scanf("%d",&b1); else if(m==2)scanf("%d%d",&b1,&b2); f[0]=1; int maxx=(1<<n)-1; for(int i=1;i<=maxx;i++) { int x=i,y=lowbit(x); dist[i]=dist[i^y]+dist[y]; if(dist[i]==b1||dist[i]==b2)continue; while(y) { f[i]+=f[i^y]; if(f[i]>=MOD)f[i]-=MOD; x^=y; y=lowbit(x); } } printf("%d\n",f[maxx]); return 0; }