UOJ Logo Universal Online Judge

UOJ

#259. 子集计数问题

统计

给定无向图 $G=(V,E)$,$\lvert V\rvert=n$,$\lvert E\rvert=m$,$V$ 中的点编号为 $1,2,...,n$。求有多少个子集 $V'\subseteq V$ 满足 $\lvert V'\rvert=k$ 且 $\forall (u,v)\in E,u\not\in V'\lor v\not\in V'$。由于答案可能很大,只需输出答案对 $p$ 取模的结果。

输入格式

本题为提交答案题。所有输入数据 subset1.in ~ subset10.in 见输入数据下载。

输入第 $1$ 行包含 $4$ 个用空格分隔的正整数 $n, m, k, p$,分别表示 $\lvert V \rvert, \lvert E \rvert$,要求的 $\lvert V' \rvert$ 的大小以及模数。

随后 $m$ 行,每行包含 $2$ 个用空格分隔的正整数 $a_i$,$b_i$,描述 $G$ 中的边 $(a_i,b_i)\in E$。

输出格式

针对给定的 $10$ 个输入文件 subset1.in ~ subset10.in,你需要分别提交你的输出文件 subset1.out ~ subset10.out。

输出文件共 $1$ 行,包含 $1$ 个整数,表示子集 $V'$ 的个数对 $p$ 取模的值。

样例一

input

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

output

6

explanation

共有 $6$ 个这样的子集 $V'$,分别是:$\{1,5\}$,$\{1,6\}$,$\{2,3\}$,$\{2,4\}$,$\{2,6\}$,$\{4,5\}$。

样例二

input

17 16 5 10000
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
7 11
8 12
8 13
10 14
10 15
12 16
15 17

output

1528

评分方式

本题共有 $10$ 个测试点,每个测试点都有一定分值。对于每个测试点,如果选手的输出与标准答案一致,则得到该测试点的分值,否则不得分。每个测试点的分值由下表给出:

测试点编号 分值 测试点编号 分值
1 $5$ 6 $11$
2 $6$ 7 $9$
3 $14$ 8 $13$
4 $8$ 9 $7$
5 $12$ 10 $15$

如何测试你的输出

在终端中先切换到该试题的目录下:(windows用户请使用cmd)

cd subset

我们提供 checker 这个工具来测试你的输出文件是否正确。使用这个工具的方法是,在终端中运行

./checker <case_no>

其中 case_no 是测试数据的编号。例如

./checker 3

将测试 subset3.out 是否正确。(windows用户请使用 checker 3

在你调用这个程序后,checker 将根据你给出的输出文件给出测试的结果。

来源

WrongAnswer

下载

输入数据及checker下载


或者逐个上传: