桌面有N張A型牌，M張B型牌，目前玩家可抽一張牌(盲抽)，若抽到A牌則可再抽兩張，若抽到B牌，則可減少對方若干生命值；
不同的B型牌可減少對方不同的生命值。問玩家在本輪抽牌中，消滅對手的概率為多少。

由于題目中N+M<=20，HP<=1000，暴力狀壓就可以了；DP[X][A][BS][HP]代表當前有X次抽拍機會，場上剩余A張A型牌，場上剩余B型牌的狀態(tài)為BS，對方生命值剩余HP時，在本輪消滅對手的概率。

狀態(tài)轉(zhuǎn)移：

1. 若A型牌有剩余，抽中A型牌的轉(zhuǎn)移 DP[X+1][A-1][BS][HP]，轉(zhuǎn)移概率為 A/(A+B)；
2. 枚舉可取的B型牌Bi，抽中Bi的轉(zhuǎn)移 DP[X-1][A][BS-{Bi}][HP-Di]，轉(zhuǎn)移概率為 1/(A+B)；

本以為復雜度稍高，可能超時，但實際上沒有問題，數(shù)據(jù)沒有很刁鉆。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

struct frac{
    long long top,low;
    frac(long long t,long long l){
        top = t;
        low = l;
    }
    frac(){}
};

long long gcd(long long a, long long b){
    if (b==0) return a;
    else return gcd(b,a%b);
}

frac add(frac a, frac b){
    long long top = a.top*b.low+b.top*a.low;
    long long low = a.low*b.low;
    long long GCD = gcd(top, low);
    top /= GCD;
    low /= GCD;
    return frac(top,low);
}

frac mul(frac a, frac b){
    long long top = a.top*b.top;
    long long low = a.low*b.low;
    long long GCD = gcd(top, low);
    top /= GCD;
    low /= GCD;
    return frac(top, low);
}

int m;
int d[25];
frac calc(int x, int a, int bs, int hp){
    if (hp<=0) return frac(1,1); //邊界，對方生命值低于等于0
    if (x==0) return frac(0,1); //邊界，當前已經(jīng)不可抽牌
    if (a+bs<=0) return frac(0,1); //邊界，場上已經(jīng)無牌可抽
    frac ans(0,1);
    int bc = 0;
    for (int i=0;i<m;i++){
        if (bs&(1<<i)) bc++;
    }
    if (a>0) ans = add(ans, mul(calc(x+1,a-1,bs,hp), frac(a,a+bc))); //抽A牌的轉(zhuǎn)移
    for (int i=0;i<m;i++){ //枚舉抽中B牌的轉(zhuǎn)移
        if (bs&(1<<i)) {
            ans = add(ans, mul(calc(x-1,a,bs-(1<<i),hp-d[i]),frac(1,a+bc)));
        }
    }
    return ans;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int hp,n;
        scanf("%d%d%d",&hp,&n,&m);
        for (int i=0;i<m;i++) scanf("%d",&d[i]);
        frac ans = calc(1,n,(1<<m)-1,hp);
        printf("%I64d/%I64d\n",ans.top, ans.low);
    }

    return 0;
}