Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) C. Felicity is Coming!组合学+集合

My Solution

题意：给出n组数，每组gi个数，每个数属于1~m，每个数可以变化但变化前相同的数变化后依然相同，变化前不同的速变化后依然不同，且可能不变，但经过变化后每组的每种数的个数不会变化，求变化的总方案数。

组合学+集合

//这题是根据Codeforces的官方题解写的

把1~m分成一些集合，在同一个集合里的数在各个gi里它们的个数都是相等的，比如一个集合里有x、y，则xy在所有gi里的个数是相等的，但x在2个不同的集合里的个数可能不同，但x的个数必然等于y的个数。而方案数就是这些集合元素的个数的阶乘的积。

把这些数储存到vector< vector > vec(m)里，vec[i]表示数i出现的gi的i，出现几次就是几个i，

记录完后，把vec排序，

然后扫一遍把当前vec和前一个vec比较，如果和前一个满足上面所说的集合条件则这2个vec是逻辑相等的，cnt++。如果不相等ans = mod(ans * factor[cnt]); cnt = 1;

复杂度 O(nlogn)

此外，如果求 a % b，经过实验 a - a / b * b 确实比 a % b 运算更快一些。

如图第2、3个用的是 a - a/b*b，第1、4个用的是 a % b
似乎确实inline LL mod(const LL x){return x - x / MOD * MOD;} 比 % 快一些。

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;
const LL MOD = 1e9 + 7;

LL factor[maxn];
inline LL mod(const LL x)
{
    return x - x / MOD * MOD;
}
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 5;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    factor[0] = factor[1] = 1;
    for(int i = 2; i < maxn; i++){ factor[i] = mod(factor[i - 1] * i); } int n, m, gi, x; cin >> n >> m;
    vector<vector> vec(m);

    int i, j;
    for(i = 0; i < n; i++){ cin >> gi;
        for(j = 0; j < gi; j++){ cin >> x;
            vec[x-1].push_back(i);
        }
    }

    for(i = 0; i < m; i++){
        sort(vec[i].begin(), vec[i].end());
    }
    sort(vec.begin(), vec.end());//化O(n^2) 为O(nlogn)

    LL ans = 1, cnt = 1;
    for(i = 1; i < m; i++){
        if(vec[i] == vec[i - 1]){
            cnt++;
        }
        else{
            ans = mod(ans * factor[cnt]);
            cnt  = 1;
        }
    }
    ans = mod(ans * factor[cnt]);

    cout << ans << endl;



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx