题意：共n张无中生有，m张攻击牌。每张攻击牌攻击力已知，敌方有p点血。随机洗牌。游戏开始，己方抽取一张手牌，若是无中生有则可再抽两张牌。求能在第一回合内将敌方杀死的概率。
n+m <= 20, p <= 1000;
很明显，与卡特兰数有关，原先栈内数量为1，抽到无中生有即入栈，否则出栈。
枚举攻击牌，求出该攻击牌组合下，用完所有手牌将对方杀死的方案数，以及抽光所有牌将对方杀死的方案数（手牌有剩）。
不算预处理的复杂度，每组数据的时间复杂度为O(2^m)
#include <cstdio>
typedef long long ll; int bc[<<], sum[<<], tmp[<<];
int C[][];
ll fact[]; ll gcd(ll a, ll b){
return b == ? a :gcd(b, a%b);
} void init(){
int i, j;
bc[] = ;
for (i=; i<(<<); i++) bc[i] = bc[i^(i&-i)] + ;
fact[] = ;
for (i=; i<=; i++) fact[i] = fact[i-] * i;
C[][] = ;
for (i=; i<=; i++){
C[i][] = C[i][i] = ;
for (j=; j<i; j++) C[i][j] = C[i-][j] + C[i-][j-];
}
} int main(){
ll a, b, d;
int p, n, m, t, i;
init();
scanf("%d", &t);
while (t --){
scanf("%d %d %d", &p, &n, &m);
for (i=; i<m; i++) scanf("%d", &tmp[<<i]);
sum[] = ;
for (i=; i<(<<m); i++) sum[i] = sum[i^(i&-i)] + tmp[i&-i];
a = ;
for (i=; i<(<<m); i++){
if (sum[i] >= p && bc[i] <= n + ){
//C(n + m − 1,m) − C(n + m − 1,m − 1)
//手牌用完，到(bc[i], bc[i])的方案数，即到(bc[i], bc[i]-1)的方案数, 需要bc[i]-1张无中生有
a += C[n][bc[i]-] * (C[ bc[i]+bc[i]- ][ bc[i]- ] - C[ bc[i]+bc[i]- ][ bc[i]- ])* fact[bc[i]-] * fact[bc[i]] * fact[n+m-*bc[i]+];
//手牌用不完, 到(n+1, m)的方案数
if(bc[i] == m&&bc[i] < n+)
a += (C[ m+n ][ m ] - C[ m+n ][ m- ])* fact[n] * fact[m];
}
}
b = fact[n+m];
d = gcd(a, b);
printf("%I64d/%I64d\n", a / d, b / d);
}
return ;
}
当时写的时候是以 状态表示的牌将敌方杀死 作为结束点，似乎还要容斥，比如用1,2,3杀死对方和用1,2就杀死对方，复杂度也可能会爆炸；
其实应该换一个角度，考虑手牌用光将对方杀死，再加上手牌用不光的case，终点已知，那么就不会有容斥关系。