[ccAUG14] Little Elephant and T-Shirts

2014-10-28
竞赛题解 / 搜索
CodeChef

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

样例输入 SampleInput

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

样例输出 SampleOutput

4
4

CodeChef TSHIRTS

代码 Code

用 f[i][j] 表示到 i 这个状态用了前 j 件衣服的方案数。其中 i 为二进制状态压缩，1 和 0 表示其是否已经分配到衣服。

读入略麻烦~~(>_<)~~

#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][105];
char ch;
vector <ll> v[105];
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;
}