[TCO2016 Round 2B DIV1 Middle] FoxAndGemstone

    题意：有n个背包，每个背包里有若干个宝石，宝石最多有16种，用'A'~'P'来表示。每个背包中所有的宝石用一个字符串来表示。已知每种宝石重量都是不等的正实数，且可以通过一个天平比较两种宝石哪个更重。询问对于任意情况下（对于任意的宝石重量的排列），能否都判断出n个背包中最重的背包是哪个（相同重量的背包都算最重的）。

    题解：首先去除那些完全一样的背包。接下来我们计算对于每一个背包，其为重量最大的背包的16个宝石的重量排列方案数，如果方案数之和为\(16!\)则为Possible，否则为Impossible。这个方案数的统计利用了这个性质：背包a比背包b重的重要条件为\(cnt[a][j]>=cnt[b][j]\)，其中\(cnt[x][j]\)表示的是背包x中重量大于等于j的宝石数目。

    首先枚举重量最大的背包。那么接下来我们可以枚举当前最小的宝石，利用数位dp进行状态转移。用16位二进制数S表示当前选出的最重的若干个宝石，\(f[S]\)表示方案数，显然\(f[S]>0\)仅当当前背包选出的S中的宝石数量大于等于其他背包中选出的S中的宝石数量。若S中包含第x个宝石，设x为S中最小的，则\(f[S]\)肯定可以由\(f[S\setminus x]\)中的所有方案末尾加上宝石x转移而来，据此计算f[S]。

    时间复杂度\(O(n2^mm)\)，其中\(m=16\)。

#include <bits/stdc++.h>
using namespace std;

int num[50][16];
int valid[50][65536];
int q[65536];
long long f[65536];
int n;

int Cnt2_1(int x)
{
	int res=0;
	while (x)
	{
		res+=x&1;
		x>>=1;
	}
	return res;
}

bool cmp(const int &a,const int &b)
{
	return Cnt2_1(a)<Cnt2_1(b);
}

typedef vector <string> :: iterator it;

class FoxAndGemstone {
public:
	string isPossible(vector <string> bags) {
		for (it i=bags.begin();i!=bags.end();i++)
			sort(i->begin(),i->end());
		sort(bags.begin(),bags.end());
		int n=unique(bags.begin(),bags.end())-bags.begin();
		memset(valid,0,sizeof(valid));
		memset(num,0,sizeof(num));
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<bags[i].length();j++)
				num[i][bags[i][j]-'A']++;
		}
		for (int i=0;i<65536;i++)
		{
			int cnt[50];
			memset(cnt,0,sizeof(cnt));
			for (int j=0;j<16;j++) if (i&(1<<j))
			for (int k=0;k<n;k++)
					cnt[k]+=num[k][j];
			int maxv=*max_element(cnt,cnt+n);
			for (int j=0;j<n;j++) if (cnt[j]==maxv) valid[j][i]=1;
		}
		for (int i=0;i<65536;i++) q[i]=i;
		sort(q,q+65536,cmp);
		long long ans=1;
		for (int i=2;i<=16;i++) ans*=(long long)i;
		for (int i=0;i<n;i++)
		{
			memset(f,0,sizeof(f));
			f[0]=1;
			for (int j=0;j<65536;j++) 
			{
				int x=q[j];
				if (!valid[i][x]) continue;
				for (int k=0;k<16;k++) if (x&(1<<k))
					f[x]+=f[x^(1<<k)];
			}
			ans-=f[65535];
		}
		printf("%lld\n",ans);
		if (ans==0) return "Possible";else return "Impossible";
	}
};