班服
(shirt.pas/.c/.cpp)
时间限制：1s；内存限制 128MB
题目描述：
要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod 1000000007后的答案。
输入描述：
共有T组数据。
对于每组数据，第一行为一个整数n，表示有n个班级。
2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。
输出描述：
对于每组数据，输出方案总数 mod 1000000007后的答案。
样例输入：
2
3
5 100 1
2
5 100
2
3 5
8 100
样例输出：
4
4
数据范围：
对于30%的数据，1<=T<=3, 1<=n<=3，每班待选样式不超过10种。
对于50%的数据，1<=T<=5, 1<=n<=5，每班待选样式不超过50种。
对于100%的数据，1<=T<=10, 1<=n<=10，每班待选样式不超过100种。
思路：
此题在考试时用for循环暴力，过了40%。
正确方法：状压DP
数据n范围较小（10），可以用二进制数来表示n被选择的状态，末状态是(1<<n)-1。要处理班级与服装的关系，需在读入时让服装来存储班级的信息才能方便转移。
参考代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+;
int T,n,x,mp[][],f[][<<];
int main()
{
scanf("%d",&T);
while(T--)
{
memset(mp,,sizeof(mp));
memset(f,,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;++i)
{
while()
{
scanf("%d",&x);
mp[x][++mp[x][]]=i;
char ch=getchar();
if(ch=='\n') break;
}
}
f[][]=;
for(int i=;i<=;++i)
for(int j=;j<(<<n);++j)
{
f[i][j]+=f[i-][j];
for(int k=;k<=mp[i][];++k)
if(j&(<<mp[i][k]-))
(f[i][j]+=f[i-][j-(<<mp[i][k]-)])%=mod;
}
printf("%d\n",f[][(<<n)-]);
}
return ;
}