[HAOI2012]容易题(EASY)

题号 NC19989
名称 [HAOI2012]容易题(EASY)
来源 [HAOI2012]

题目描述

为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：

有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 mod 1000000007的值，是不是很简单呢？呵呵！

样例

输入
3 4 5
1 1
1 1
2 2
2 3
4 3
输出
90

样例解释
A[1]不能取1
A[2]不能去2、3
A[4]不能取3
所以可能的数列有以下12种
数列      积
2 1 1 1     2
2 1 1 2     4
2 1 2 1     4
2 1 2 2     8
2 1 3 1     6
2 1 3 2     12
3 1 1 1     3
3 1 1 2     6
3 1 2 1     6
3 1 2 2     12
3 1 3 1     9
3 1 3 2     18

算法

(数学 + 快速幂)

假如没有限制，题意类似于给你m个1 ~ n的数的集合，（1,2,...,n）、（1,2,...,n）、...分别从这些集合中选一个数相乘，求所有这些乘积之和，如果我们将这些集合（1,2,...,n）、（1,2,...,n）、...，写成(1 + 2 + ... + n) * (1 + 2 + ... + n) * ... 的形式，根据我们的运算习惯我们会将这些括号展开一个一个求解，即先从第一个括号中拿1，然后从第二个括号中再拿1，...，从最后一个括号中拿1，相乘（1 * 1 * ...1）得1，然后再从从第一个括号中拿1，然后从第二个括号中再拿1，...，从最后一个括号中拿2，相乘（1 * 1 * ...2）得2，重复这样的操作，我们可以发现这种操作正好和题目要求的运算是一致的，也就是说(1 + 2 + ... + n) * (1 + 2 + ... + n) * ... 的结果就是答案，(1 + 2 + ... + n) 我们可以O（1）求出来，有m项相乘我们可以用快速幂优化。加上限制条件，我们就将(1 + 2 + ... + n)中去掉一些数再相乘，只有k个限制需要特殊处理时间复杂度是可以的，要注意的细节是可能有多个相同的限制所以我们需要去重，可以用set来维护。

时间复杂度

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int,LL> PII;
set<PII> S;
const int N = 100010,mod = 1000000007;
int n,m,k;

LL qmi(LL a,int k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

void solve()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < k;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        S.insert(make_pair(x,y));
    }
    LL sum = (n + 1ll) * n / 2 % mod;
    LL res = 1ll;
    PII tmp = make_pair(-1,(sum - 1) % mod);
    int cnt = 0;
    for(auto &t : S)
    {
        if(t.first != tmp.first)
        {
            res = (res * (sum - tmp.second)) % mod;
            tmp = t;
            cnt ++;
        }else tmp.second = (tmp.second + t.second) % mod;
    }
    res = (res * (sum - tmp.second)) % mod;
    res = (res * qmi(sum,m - cnt)) % mod;
    // cout << S.size() << endl;
    printf("%lld\n",(res % mod + mod) % mod);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}