HDU-5816 状压DP [2016多校]

桌面有N张A型牌，M张B型牌，目前玩家可抽一张牌(盲抽)，若抽到A牌则可再抽两张，若抽到B牌，则可减少对方若干生命值；
不同的B型牌可减少对方不同的生命值。问玩家在本轮抽牌中，消灭对手的概率为多少。

由于题目中N+M<=20，HP<=1000，暴力状压就可以了；DP[X][A][BS][HP]代表当前有X次抽拍机会，场上剩余A张A型牌，场上剩余B型牌的状态为BS，对方生命值剩余HP时，在本轮消灭对手的概率。

状态转移：

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

本以为复杂度稍高，可能超时，但实际上没有问题，数据没有很刁钻。

#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); //边界，当前已经不可抽牌
    if (a+bs<=0) return frac(0,1); //边界，场上已经无牌可抽
    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牌的转移
    for (int i=0;i<m;i++){ //枚举抽中B牌的转移
        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;
}