状压dp计算方案数。
dp[s]表示抽到s状态的牌的方案数有几种。
如果s状态已经获胜，那么答案可以加上dp[s]*剩余未抽的牌的全排列数，该状态不再向后转移。
如果s状态未获胜，但是还可以抽牌，那么方案数往后转移。
如果s状态未获胜，且不能抽牌，那么该状态也不再向后转移。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } int T,n,m,p,w[25]; LL dp[(1<<20)+10], f[25],ans; LL gcd(LL a,LL b) { if(b==0) return a; return gcd(b,a%b); } int get(int a,int L,int R) { int res=0; for(int i=L;i<=R;i++) if(a&(1<<i)) res++; return res; } int main() { f[0]=1; for(int i=1;i<=20;i++) f[i]=i*f[i-1]; scanf("%d",&T); while(T--) { scanf("%d%d%d",&p,&n,&m); for(int i=1;i<=m;i++) scanf("%d",&w[i]); memset(dp,0,sizeof dp); for(int i=0;i<n+m;i++) dp[1<<i]=1; ans=0; for(int i=0;i< 1<<(n+m);i++) { int A=get(i,0,n-1),B=get(i,n,n+m-1); int sum=0; for(int j=n;j<=n+m-1;j++) if(i&(1<<j)) sum=sum+w[j-n+1]; if(sum>=p) { ans=ans+dp[i]*f[n+m-A-B]; continue;} if(A<B) continue; for(int j=0;j<n+m;j++) if((i&(1<<j))==0) dp[i|(1<<j)]=dp[i|(1<<j)]+dp[i]; } if(ans==0) printf("0/1 "); else { LL GCD=gcd(f[n+m],ans); printf("%lld/%lld ",ans/GCD,f[n+m]/GCD); } } return 0; }