[HAOI 2012] 容易题

题目大意

给定一个有 mm 个元素的数列 {ai}\{a_i\},有 1ain1 \leqslant a_i \leqslant n,并且对于一些 aia_i 有些值不能取(一共有 kk 个限制)。我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的数列的积h的和模 1,000,000,0071,000,000,007 的值。

1n,  m1,000,000,0001 \leqslant n, \; m \leqslant 1,000,000,000

1k100,0001 \leqslant k \leqslant 100,000

题目链接

【HAOI 2012】容易题 - Luogu 2220

题解

所求数列积的和即为(意会证明吧。。。):

i=imj=1nj×[j]\prod_{i = i}^{m} \sum_{j = 1}^{n} j \times [j可选]

对限制排序,有限制的位从 i=1ni\sum_{i = 1}^{n}i 中减去对应的值并乘进答案,剩下的用快速幂计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
const int MAXK = 100005;
const int MOD = 1000000007;
struct Taboo {
int pos, val;
bool operator<(const Taboo &another) const {
return pos == another.pos ? val < another.val : pos < another.pos;
}
} T[MAXK];
long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < k; i++) scanf("%d %d", &T[i].pos, &T[i].val);
std::sort(T, T + k);
long long sum = (long long) n * (n + 1) / 2 % MOD, temp = sum;
long long ans = 1;
for (int i = 0; i < k; i++) {
if (i != 0 && T[i].pos != T[i - 1].pos) {
ans = ans * temp % MOD;
temp = sum;
m--;
}
if (i == 0 || T[i].pos != T[i - 1].pos || T[i].val != T[i - 1].val)
temp = (temp + MOD - T[i].val) % MOD;
}
m--;
ans = ans * temp % MOD;
printf("%lld\n", ans * pow(sum, m) % MOD);
return 0;
}