洛谷P2396 yyy loves Maths VII 题解
题目链接:P2396 yyy loves Maths VII
题意:
一群同学在和 yyy 玩一个游戏。
每次,他们会给 yyy \(n\) 张卡片,卡片上有数字,所有的数字都是“幸运数字”,我们认为第 \(i\) 张卡片上数字是 \(a_{i}\)。
每次 yyy 可以选择向前走 \(a_{i}\) 步并且丢掉第 \(i\) 张卡片。当他手上没有卡片的时候他就赢了。
但是呢,大家对“厄运数字”的位置布置下了陷阱,如果 yyy 停在这个格子上,那么他就输了。注意:即使到了终点,但是这个位置是厄运数字,那么也输了。
现在,有些同学开始问:yyy 有多大的概率会赢呢?
大家觉得这是个好问题,有人立即让 yyy 写个程序:“电脑运行速度很快!\(24\) 的阶乘也不过就 \(620\,448\,401\,733\,239\,439\,360\,000\),yyy 你快写个程序来算一算。”
yyy 表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是对 \(10^9+7\) 取模后的值。
大家都不会写程序,只好妥协。
但是这时候 yyy 为难了,\(24!\) 太大了,要跑好长时间。
他时间严重不够!需要你的帮助!
由于 yyy 人格分裂,某个数字可能既属于幸运数字又属于厄运数字。
\(50\%\) 的数据 \(n \leq 23\) , \(100\%\) 的数据 \(n \leq 24\)。
注意到 \(n \le 24\) ,并且每张牌只能用一次,考虑状压dp。
对于每个状态 \(i\) ,枚举它是从哪个地方转移来的
具体地,设 \(f_i\) 表示状态为 \(i\) 的方案数,则 \[ f_i = \sum f_{i \setminus \{j\}} \times [j \in i] \] 显然答案为 \(f_{\text{mx}} , \text{mx}= 2^n -1\)。
同时我们还要记录一个 \(\text{dis}_i\) 表示 \(i\) 状态对应的路径长
当 \(\text{dis}_i\) 为“厄运数字”时,不转移 \(f_i\) ,即 \(f_i = 0\) 。
时间复杂度 \(O(n 2^n)\) ,卡常题。
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)((1<<24)+5)
const int p=1e9+7;
int n,m,b0,b1; signed dis[N],f[N];
template<typename T> void add(T &x,T y){x=(x+(y%p))%p;}
void solve(int x)
{
for(int i=x,j; i; i^=j) j=i&(-i),add(f[x],f[x^j]);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=0; i<n; i++) cin >> dis[1 << i];
cin >> m;
if(m>0) cin >> b0;
if(m>1) cin >> b1;
f[0]=1;
int mx=(1<<n)-1;
for(int i=1,j; i<=mx; i++)
{
j=i&(-i); dis[i]=dis[i^j]+dis[j];
if(dis[i]!=b0&&dis[i]!=b1) solve(i);
}
cout << f[mx] << '\n';
return 0;
}