Codecraft-17 and Codeforces Round #391 - C

题目链接：http://codeforces.com/contest/757/problem/C

题意：给定n个gym和m个Pokemon的类型，然后给你每个gym内的Pokemon未进化之前的类型，问你存在多少种可行的进化方式。每种进化方式要满足进化后每个gym的类型和个数和进化后的每个gym的类型和个数都要一致。

思路：从Examples可以得到结论，对于类型x和类型y，只有当x在每个gym出现的个数与y在每个gym出现的个数相同时。类型x,y可以交换，即f(x)=y,f(y)=x是符合题目要求的，由于从gym入手解决问题比较苦难，并且进化之和两个类型有关，所以我们从类型入手。对于第i个gym的类型j，我们利用vector把i保存在j中。最后如果x,y的vector里的gym序列相同的话说明可以互相转换。 由于vector容器重载了<运算符和==运算符。所以可以很方面地进行判断。  最后就是计算共享了，其实就是个排列数的问题。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<stdio.h>

#include<queue>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<time.h>

#include<cmath>

using namespace std;

typedef long long int LL;

const int MAXN = 1e6 + ;

const int mod = 1e9 + ;

vector<int>G[MAXN];

int main(){

//#ifdef kirito

//    freopen("in.txt", "r", stdin);

//    freopen("out.txt", "w", stdout);

//#endif

//    int start = clock();

    int n,m,k,num;

    while (~scanf("%d%d", &n,&m)){

        for (int i = ; i <= m; i++){

            G[i].clear();

        }

        for (int i = ; i <= n; i++){

            scanf("%d",&k);

            for (int j = ; j <= k; j++){

                scanf("%d", &num);

                G[num].push_back(i);

            }

        }

        sort(G + , G + m + );

        LL ans = ,cnt=;

        for (int i = ; i <= m; i++){

            if (G[i] == G[i - ]){

                cnt++;

                ans = (1LL*ans*cnt)%mod;

            }

            else{

                cnt = ;

            }

        }

        printf("%I64d\n", ans);

    }

//#ifdef LOCAL_TIME

//    cout << "[Finished in " << clock() - start << " ms]" << endl;

//#endif

    return ;

}