题目描述：
要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod 1000000007后的答案。
输入描述：
共有T组数据。
对于每组数据，第一行为一个整数n，表示有n个班级。
2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。
输出描述：
对于每组数据，输出方案总数 mod 1000000007后的答案。
样例输入：
2
2
3 5
8 100
3
5 100 1
2
5 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种。
分析:
如果注意到n
10 应该发现这是道状态压缩题.
考试的时候一直当成计数题做.然而想多了.
其实就是将班级状态压缩.然后根据校服来进行转移.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<cstdio>//BAONI #include<cstring> #include<algorithm> using namespace std; template<class T>void read(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } x = f ? -x : x; return ; } const int Mod=1000000007; int n; int F[110][1050]; int A[20][110]; int main() { freopen("shirt.in","r",stdin); freopen("shirt.out","w",stdout); int t; read(t); while(t--) { memset(F,0,sizeof(F)); memset(A,0,sizeof(A)); read(n); //printf("%d\n",n); for(int i=1;i<=n;++i) { int k=0;char ch=getchar(); while(true) { if(ch<'0'||ch>'9'){ A[i][k]=1; k=0; } if(ch<='9'&&ch>='0'){ k=(k<<1)+(k<<3)+(ch^48); } ch=getchar(); if(ch=='\n')break; } A[i][k]=1; } /* for(int i=1;i<=n;++i) { for(int j=1;j<=100;++j) if(A[i][j])printf("%d ",j); printf("\n"); } */ F[0][0]=1; for(int i=1;i<=100;++i) { for(int j=0;j<(1<<n);++j) { F[i][j]=F[i-1][j]; } for(int j=1;j<=n;++j) { if(!A[j][i])continue; for(int k=0;k<=(1<<n)-1;++k) { if(k&(1<<(j-1)))continue; F[i][k+(1<<(j-1))]=(F[i][k+(1<<(j-1))] + F[i-1][k])%Mod; } } } /* for(int i=1;i<=100;++i) { for(int j=1;j<=(1<<n)-1;++j) printf("%d ",F[i][j]); printf("\n"); } */ int tot=(1<<n)-1; printf("%d\n",F[100][tot]); } fclose(stdin); fclose(stdout); return 0; } |
