[洛谷 2396]yyy loves Maths VII

题目链接

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;
}