SSL 2676_数学_模拟

lzusa 发布于 2017-08-10 1 次阅读

题目描述

小A得到了一个数列A，他告诉你这个数列中所有的A[i]都是1到n的自然数，并且告诉你对于一些A[i]不能取哪些值。无聊的你想要知道所有可能的数列的积的和。定义一个数列的积为这个数列所有数的乘机。由于答案太大，只要模10^9+7输出即可。

 

思路

首先有一个规律就是ans为每一项中没有被限制的数相加让后相乘

显然这样直接暴力会T，数据中的限制有 $10^5$ 个，而总数则有$10^9$ 个

所以没有限制条件的数量还是很多的，我们就可以用一个快速幂加上暴力来求解

#include 
#include 
#include 
using namespace std;
#define p 1000000007
#define maxn 100001
struct arr
{
    long long x, y;
}a[maxn];
long long tot;
long long read()
{
    long long x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch -'0'; ch = getchar();}
    return x;
}
long long cmp(arr a, arr b)
{
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
long long fast(long long x)
{
    if (x == 0) return 1;
    if (x == 1) return tot;
    long long t = fast(x / 2) % p;
    if (x % 2 == 1) return (((t * t) % p) * (tot % p)) % p;
    else return (t * t) % p;

}
int main()
{
    long long n, m ,k;
    cin >> n >> m >> k;
    for (long long i = 1; i <= k; i++)
    {
        a[i].x = read();
        a[i].y = read();
    }
    sort(a + 1, a + k + 1, cmp);
    for (long long i = 1; i < k; i++)
        if (a[i].x == a[i + 1].x && a[i].y == a[i + 1].y) a[i].y = 0;
    tot = ((1 + n) * n) / 2;
    long long i = 0, ans = 1, now = 1, sum = m;
    while (i < k)
    {
        i++;
        if (a[i].x != a[i - 1].x)
        {
            ans = (ans * (now % p)) % p;
            sum--;
            now = tot;
        }
        if (a[i].y != 0) now -= a[i].y;
    }
    ans = (ans * (now % p)) % p;
    ans = (ans * fast(sum)) % p;
    cout << ans << endl;
}

 

]]>