题目
题目描述
为了使得大家高兴,小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))m−cnt 对于上式
…
\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
;
}
res
+= quick_power(tot
, m
- ssize
, mod
);
for (int i
= 1; i
<= ssize
; ++i
) {
res
= (res
* s
[i
] + mod
) % mod
;
}
write(res
), putchar('\n');
return 0;
}