Codeforces Round #391 C. Felicity is Coming!

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

题意：给你n组数范围在1～m，可进行变换f(x)=y,就是将所有的x全变成y，最后

要满足变化后每组数的种类和原来一样。

拿样例来说

2 3

2 1 2

2 2 3

1在第一组里，2在第1，2组里，3在第3组里

1能变1或2，1变2后2只能变1，但是第二组里没有1所以不能变，

所以总共只有1种变法。

其实这题就是分集合该样例可分为3个集合

集合1={1},2={1,2},3={2}（集合表示出现在哪组里）如果集合完全相同那么结果就是乘上相同集合数的阶乘

这里可以sort一下vector数组，直接sort的结果是先按照首元素为第一优先级然后次元素次之，以此类推来拍的。

该样例sort后的结果是vc[1]={1},vc[2]={1,2},vc[3]={2};这样比较起来就方便了。

#include <iostream>

#include <algorithm>

#include <vector>

#define mod 1000000007

typedef long long ll;

using namespace std;

const int M = 1e6 + 10;

vector<int> vc[M];

int main() {

    int n , m;

    cin >> n >> m;

    int g , gg;

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

        cin >> g;

        for(int j = 0 ; j < g ; j++) {

            cin >> gg;

            vc[gg].push_back(i + 1);

        }

    }

    sort(vc + 1 , vc + 1 + m);

    ll ans = 1 , k = 1;

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

        if(vc[i] == vc[i - 1]) {

            k++;

            ans = (ans * k) % mod;

        }

        else

            k = 1;

    }

    cout << ans << endl;

    return 0;

}

巴特西

Codeforces Round #391 C. Felicity is Coming!

最新文章

热门文章