# [ccAUG14] Little Elephant and T-Shirts

## 描述 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.

## 输入格式 InputFormat

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.

## 输出格式 OutputFormat

For each test case, print in single line the required number of ways modulo 1000000007 = 109+7.

2
2
3 5
8 100
3
5 100 1
2
5 100

4
4

CodeChef TSHIRTS

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
const ll mod=1000000007;
ll i,j,t,n,m,l,r,k,z,y,x;
ll T;
ll f[(1<<10)+5];
char ch;
vector <ll> v;
inline bool read(ll &x,ll t)
{
x=0;char ch=getchar();
if (ch=='\n') return false;
while (ch<'0' || ch>'9')
{
ch=getchar();
if (ch=='\n') return false;
}
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
v[x].push_back(t);
if (ch=='\n') return false;
return true;
}
ll find(ll m,ll k)
{
ll i,j,t,ans;
if (k>100)
{
if (m==(1<<n)-1) f[m][k]=1;
else f[m][k]=0;
return f[m][k];
}
if (f[m][k]!=-1) return f[m][k];
ans=0;
ans+=find(m,k+1);
t=v[k].size();
for (i=0;i<t;i++)
{
if (m&(1<<v[k][i])) continue;
ans+=find(m|(1<<v[k][i]),k+1);
if (ans>=mod) ans-=mod;
}
f[m][k]=ans;
return f[m][k];
}
int main()
{
scanf("%lld",&T);
while (T--)
{
memset(f,-1,sizeof(f));
for (i=0;i<=100;i++) v[i].clear();
scanf("%lld",&n);
scanf("%c",&ch);
for (i=0;i<n;i++)
{
while (read(t,i)) ;
}
for (i=1;i<=100;i++) sort(v[i].begin(),v[i].end());
printf("%lld\n",find(0,1));
}
return 0;
} ``````