记录一个菜逼的成长。。
推荐几篇好看懂的博客。 参考博客: http://blog.csdn.net/qq_21057881/article/details/52167285 http://blog.csdn.net/zzz805/article/details/52169725
我的代码，是卡过去的。。
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <deque> #include <cctype> #include <bitset> #include <cmath> using namespace std; #define ALL(v) (v).begin(),(v).end() #define cl(a) memset(a,0,sizeof(a)) #define bp __builtin_popcount #define pb push_back #define fin freopen("D://in.txt","r",stdin) #define fout freopen("D://out.txt","w",stdout) #define lson t<<1,l,mid #define rson t<<1|1,mid+1,r #define seglen (node[t].r-node[t].l+1) typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; typedef vector<PII> VPII; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; template <typename T> inline void read(T &x){ T ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; x = ans; } inline bool DBread(double &num) { char in;double Dec=0.1; bool IsN=false,IsD=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&in!='.'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){IsN=true;num=0;} else if(in=='.'){IsD=true;num=0;} else num=in-'0'; if(!IsD){ while(in=getchar(),in>='0'&&in<='9'){ num*=10;num+=in-'0';} } if(in!='.'){ if(IsN) num=-num; return true; }else{ while(in=getchar(),in>='0'&&in<='9'){ num+=Dec*(in-'0');Dec*=0.1; } } if(IsN) num=-num; return true; } template <typename T> inline void write(T a) { if(a < 0) { putchar('-'); a = -a; } if(a >= 10) write(a / 10); putchar(a % 10 + '0'); } /******************head***********************/ LL fact[21]; int x[21],countt[(1<<20) + 10]; LL dp[(1<<20)+10]; int p,n,m,tot; void init() { for( int i = 0; i < (1<<20); i++ ){ for( int j = 0; j < 20; j++ ) if(i & (1<<j))countt[i]++; } fact[0] = 1; for( int i = 1; i < 21; i++ ) fact[i] = fact[i-1] * i; } int _count(int s) { int ans = 0; for( int i = 0; i < n; i++ ){ if( s & (1<<i) )ans++; } return 2*ans - countt[s] + 1; } int damage(int s) { int ret = 0; for( int i = n; i < tot; i++ ){ if(s & (1<<i))ret+=x[i]; } return ret; } int main() { init(); int T;read(T); while(T--){ cl(dp); read(p),read(n),read(m); tot = n + m; for( int i = n; i < tot; i++ ) read(x[i]); dp[0] = 1; int all = (1<<tot) - 1; LL ans = 0; if(damage(all) >= p){ for( int s = 0; s < (1<<tot); s++ ){ if(dp[s]){ if(s == all || _count(s) == 0){//最后一个状态或者手牌数为0 //如果伤害已经大于等于p则不需要继续枚举下去，取剩余的排列数即可 if(damage(s) >= p)ans += dp[s] * fact[tot-countt[s]]; } else { for( int i = 0; i < tot; i++ ){ if(!(s & (1<<i))){//这张牌如果不是手牌 dp[s^(1<<i)] += dp[s];//则这个状态下再抽一张牌的个数是加上这个状态的方案数 } } } } } } LL y = fact[tot]; LL gcd = __gcd(ans,y); write(ans/gcd);putchar('/');write(y/gcd);puts(""); } return 0; }