Problem Description
Little Elephant and his friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts of the
same ID.
They want to know how many arrangements are there in which no two persons wear same T-Shirt. One arrangement is considered different from another arrangement if there is at least one person wearing a different kind of T-Shirt in another arrangement.
Input
First line of the input contains a single integer T denoting number of test cases. Then T test cases follow.
For each test case, first line contains an integer N, denoting the total number of persons. Each of the next N lines contains at least 1 and at most 100 space separated distinct integers, denoting the ID's of the T-Shirts ith person has.
Output
For each test case, print in single line the required number of ways modulo 1000000007 = 109+7.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10
Example
Input:
2
2
3 5
8 100
3
5 100 1
2
5 100
Output:
4
4
Explanation
For the first case, 4 possible ways are (3,8), (3,100), (5,8) and (5,100).For the second case, 4 possible ways are (5,2,100), (100,2,5), (1,2,100), and (1,2,5).
题解
一道怪怪的题……首先dfs肯定不可取，100^10……接着考虑容斥原理，但好像条件很苛刻……我太弱，根本无法yy。然后想不出来，看了已A代码……为什么说是一道奇怪的题呢？因为我不知道A题的仁兄是怎么想到的。我们考虑f[ i ][ j ]，i表示用1~i编号以内的衣服，j是一种状态，表示每个人是否穿了衣服。假设我们现在搜到第i种衣服：1、所有人都没有这种衣服，那对于f[ i ][ j ]，j取任意状态，都=f[ i-1 ][ j ].2、有人有这种衣服，那么同样的，对于状态j，f[ i ][ j ]=f[ i-1 ][ j ]，此时表示没人选择穿该种衣服（与该件衣服不存在等价）。设此人在状态中为从右往左第x位，对于状态j，若j中x还没有穿衣服，f[
i ][ j+(1<<x) ]=f[ i ][ j+(1<<x) ]+f[ i-1 ][ j ]；最终答案就是f[100][(1<<n)-1]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define mod 1000000007
using namespace std;
int T,n,a[12][102],f[102][1050];
void init()
{
scanf("%d",&n);
memset(a,0,sizeof(a));
int i,x; char ch;
for(i=1;i<=n;i++)
{while(scanf("%d%c",&x,&ch))
{a[i][x]=1;
if(ch=='\n') break;
}
}
}
void dp()
{
int i,j,k;
memset(f,0,sizeof(f));
f[0][0]=1;
for(i=1;i<=100;i++)
{for(j=0;j<(1<<n);j++)
f[i][j]=f[i-1][j];
for(j=1;j<=n;j++)
{if(!a[j][i]) continue;
for(k=0;k<(1<<n);k++)
{if(k&(1<<(j-1))) continue;
f[i][k+(1<<(j-1))]=(f[i][k+(1<<(j-1))]+f[i-1][k])%mod;
}
}
}
printf("%d\n",f[100][(1<<n)-1]);
}
int main()
{
scanf("%d",&T);
while(T--)
{init(); dp();}
return 0;
}