Problem 2776 --子集计数问题

2776: 子集计数问题

正确率: $0.00\%$ 下一题

Description

给定无向图

G=(V,E)，

∣V∣=n，

∣E∣=m，

VV 中的点编号为

1,2,...,n。求有多少个子集

V′⊆V 满足

∣V′∣=k 且

∀(u,v)∈E,u∉V′∨v∉V′。由于答案可能很大，只需输出答案对 p 取模的结果。

输入第行包含 4 个用空格分隔的正整数 n,m,k,p，分别表示 ∣V∣,∣E∣，要求的 ∣V′∣的大小以及模数。

随后 m 行，每行包含 2 个用空格分隔的正整数 ai，bi，描述 G 中的边 (ai,bi)∈E。

输出文件共

1 行，包含 1 个整数，表示子集

V′ 的个数对

p 取模的值

6 9 2 10000
1 2
1 3
1 4
4 3
2 5
5 6
3 5
3 6
6 4

6 个这样的子集

V′，分别是：

{1,5}，

{1,6}，

{2,3}，

{2,4}，

{2,6}，

{4,5}。

竞赛编号	竞赛名称	竞赛时间	访问比赛

AOJ