P2220 [HAOI2012]容易题

    xiaoxiao2022-12-08  61

    题目

    题目描述

    为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下: 有一个数列A已知对于所有的A[i]都是1~n的自然数,并且知道对于一些A[i]不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的数列的积的和 mod 1000000007的值,是不是很简单呢?呵呵!

    输入输出格式

    输入格式:

    第一行三个整数n,m,k分别表示数列元素的取值范围,数列元素个数,以及已知的限制条数。 接下来k行,每行两个正整数x,y表示A[x]的值不能是y。

    输出格式:

    一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有,答案输出0。

    输入输出样例

    输入样例#1:

    3 4 5 1 1 1 1 2 2 2 3 4 3

    输出样例#1:

    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

    数据范围

    30 30% 30的数据 n < = 4 , m < = 10 , k < = 10 n<=4,m<=10,k<=10 n<=4,m<=10,k<=10 另有 20 20% 20的数据 k = 0 k=0 k=0 70 70% 70的数据 n < = 1000 , m < = 1000 , k < = 1000 n<=1000,m<=1000,k<=1000 n<=1000,m<=1000,k<=1000 100 100% 100的数据 4 n < = 1 0 9 , m < = 1 0 9 , k < = 1 0 5 , 1 < = y < = n , 1 < = x < = m 4n<=10^9,m<=10^9,k<=10^5,1<=y<=n,1<=x<=m 4n<=109,m<=109,k<=105,1<=y<=n,1<=x<=m

    题解

    首先考虑 k = 0 k = 0 k=0,即没有限制的情况

    a n s = ( n ∗ ( n + 1 ) 2 ) m ans = (\frac{n*(n+1)}{2})^m ans=(2n(n+1))m 如果 k = ̸ 0 k =\not 0 k≠0,那么结果变为不被限制的数字乘上被限制的数字,即

    a n s = ( n ∗ ( n + 1 ) 2 ) − k i ∗ ⋯ ∗ ( n ∗ ( n + 1 ) 2 ) m − c n t ans = (\frac{n*(n+1)}{2}) -k_i * \dots *(\frac{n*(n+1)}{2})^{m-cnt} ans=(2n(n+1))ki(2n(n+1))mcnt 对于上式 … \dots 前为被限制的数列相乘,后为不被限制的数列相乘其中 c n t cnt cnt不一定等于 k k k

    code

    #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 100; const int mod = 1000000007; typedef long long LL; template <typename T> inline void read(T &s) { s = 0; T w = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); } s *= w; } template <typename T> inline void write(T s) { T w = 0, c[50]; if (s < 0) putchar('-'), s = -s; while(s) c[++w] = (s % 10) + 48, s /= 10; while(w) putchar(c[w--]); } LL n, m, k, ssize; LL tot, res; LL s[maxn]; struct del { LL x, y; } a[maxn]; inline bool cmp(del aa, del bb) { if (aa.x == bb.x) return aa.y < bb.y; else return aa.x < bb.x; } inline LL quick_power(LL x, LL y, LL p) { LL ans = 1; for (; y; y >>= 1) { if (y & 1) ans = (LL)ans * x % p; x = x * x % p; } return ans; } int main() { read(n), read(m), read(k); for (int i = 1; i <= k; ++i) read(a[i].x), read(a[i].y); tot = n * (n + 1) / 2; tot %= mod; sort(a + 1, a + k + 1, cmp); for (int i = 1; i <= k; ++i) { if (a[i].x != a[i - 1].x) s[++ssize] = tot; else if (a[i].y == a[i - 1].y) continue; s[ssize] = (s[ssize] - a[i].y + mod) % mod; // s[ssize] %= mod; } res += quick_power(tot, m - ssize, mod); for (int i = 1; i <= ssize; ++i) { res = (res * s[i] + mod) % mod; // res %= mod; } write(res), putchar('\n'); return 0; }
    最新回复(0)