问题描述　　炉石传说是暴雪出品的一款在线卡牌收集对战游戏。在这款游戏里，战术策略与运气都是影响胜负的重要因素。在你陷入绝望时，你唯一的希望就只剩下每次从牌堆上抽出那张牌，祈祷这张牌能够为你解决眼前的难题。如果你正好抽出了这张牌，我们就会把你叫做“神抽狗”。

现在，让你计算出你变成神抽狗的概率。为了简化问题，现在假设我们只有两类牌，在这问题中，卡牌费用不做考虑。

A类卡牌：假如牌堆卡牌数量少于2张，那么抽掉牌堆所有牌;否则，从牌堆顶部抽2张牌。

B类卡牌：对敌人造成X点伤害。

注意，B类卡牌中，X会有不同的取值。

开始，你的手牌数量为0。你的敌人有P点生命值(HP)。你的牌堆有N张A类卡牌，M张B类卡牌。牌堆卡牌顺序随机打乱。在你回合开始时，从牌堆顶部抽1张牌。你可以一次性用掉所有手牌。你的任务是，计算出本回合赢得对战胜利的几率，既至少对敌人造成P点伤害。

输入

第1行，是测试案例数量T(T<=10)

继而取3个正整数P(P<=100),N和M(N+M<=20)，代表了敌人HP，A类卡牌数量，和B类卡牌数量。下一行是整数M中B类卡牌的X值(0

输出

在每个案例中，输出约分后的概率(既，最大公约数只能为1)。如果得出是0(1)，则应输出0/1(1/1)。

例

输入

2

312

12

3510

1111111111

输出

1/3

46/273

解法　　#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define lson th<<1

#define rson th<<1|1

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define Key_value ch[ch[root][1]][0]

#define maxn 1100000

double dp[maxn];

int a[100];

ll po[100];

int p,n,m,weishu;

ll gcd(ll a,ll b){

if(b==0)return a;

else return gcd(b,a%b);

}

void init()

{

ll i;

po[0]=1;

for(i=1;i<=20;i++){

po[i]=i*po[i-1];

}

}

ll geshu;

int panduan(int state)

{

geshu=n+m;

int num=0,i;

for(i=0;i

if(state&(1<

if(i<=m-1){

num+=a[i];

}

geshu--;

}

}

if(num>=p)return 1;

else return 0;

}

ll dfs(int state,int cishu)

{

int i,j;

if(cishu==0){

if(panduan(state) )return po[geshu];

else return 0;

}

ll cnt=0;

int state1;

for(i=0;i<=n+m-1;i++){

if(state&(1<

if(i>=m){

state1=(state|(1<

if(dp[state1]!=-1)cnt+=dp[state1];

else{

cnt+=dfs(state1,cishu+1);

}

}

else{

state1=(state|(1<

if(panduan(state1) )cnt+=po[geshu];

else{

if(dp[state1]!=-1)cnt+=dp[state1];

else cnt+=dfs(state1,cishu-1);

}

}

}

dp[state]=cnt;

return cnt;

}

int main()

{

int i,j,T;

init();

scanf("%d",&T);

while(T--)

{

scanf("%d%d%d",&p,&n,&m);

int zong=(1<<(n+m))-1;

for(i=0;i

scanf("%d",&a[i]);

}

for(i=0;i<=zong;i++)dp[i]=-1;

ll tot=dfs(0,1);

ll t1,t2,t;

t=gcd(tot,po[n+m]);

printf("%lld/%lld\n",tot/t,po[n+m]/t);

}

return 0;

}

再逛逛>>