QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4911. 造数据

Statistics

题目背景

(注:题面较长,如果不想读题可以直接看后面的题目描述,不过题目背景部分对理解题意有一定帮助)

小C是一名菜鸡OIer。这天,小C在一次NOIP模拟赛中看到了这样一道题目:

对于一张n个点m条边的无向图,如果它的节点标号从1到n,且无重边自环,还没有孤点,那么称它是“好的”。对于“好的”无向图,定义这张图的变换为一张m个点的有向图,构造过程如下:
    1.将有向图的点与无向图的边以某种方式一一对应。
    2.对于无向图中每个点,将这个点在无向图中的出边按照终点从小到大排序,然后把这些边在有向图中对应的点按顺序连成一条链。
给定一张有向图G,已知G是由一张“好的”无向图变换得到的。现在需要给G中每个点分配一个正整数对(u,v),使得把这些(u,v)看成u到v的边之后,连成的无向图是“好的”,并且将连成的无向图变换之后,得到的有向图与G完全重合。此处的完全重合是指,在上述变换的步骤1,将G中的每个点与它在无向图中形成的边对应,然后对无向图进行变换,就能得到G。
现在请问有多少种分配数对的方式呢,由于答案可能很大,你只需要输出答案对998244353取模的值。

小C看到混乱的题面,没有理解题目的意思,因此他去看了一下下面的这个样例解释:

样例输入:
    3 2
    1 2
    1 3
样例输出:
    6
样例解释:
    下面6张图就是6种方案的无向图,每条边上面的数字代表这条边所对应的G中节点编号。

其中第一张图的变换过程如下:

可以看出G中1,2,3号点的分配数对是(1,2),(1,3)及(2,4)。

然而当小C还沉浸在终于明白题目的喜悦之中时,他发现他的神仙同学们已经开始敲键盘了。小C很慌张,他看了一眼数据范围,$n\leq 400$,由于机房的电脑非常厉害,这个数据范围明显是状压dp了。虽然小C并不会,但他会记忆化搜索,他找到了一种做法:

根据构造过程的第二步,小C按无向图标号从小到大进行搜索,每次找出一条链,满足这条链的起始点入度不为$2$,终点出度不为$2$。在这个过程中,小C将记录每个点的经过的次数,以及每一条边是否走过。小C认为两个状态本质相同,当且仅当每个点的出现次数相同而且每条边是否经过的状态也相同。

同时,小C为了减小复杂度,他会将不合法的状态排除掉,小C会对$G$中每个节点判断下面$5$个命题是否为真,如果至少有一个为真,那么他就会认为这个状态不合法,否则会认为这个状态合法:

1.这个点经过次数为$0$且它的入边和出边存在已经走过的边。

2.这个点经过次数为$2$且它的入边和出边存在还未走过的边。

3.这个点入度为$2$且这个点被走过的入边条数不等于这个点经过次数。

4.这个点出度为$2$且这个点被走过的出边条数不等于这个点经过次数。

5.这个点的出边所能到达的点经过次数最大值大于这个点经过次数。

小C使用了一种巧妙的记忆化搜索方式,使得自己的算法的时间复杂度为$O($本质不同的合法状态总数$\times n)$。他很快的实现了这个算法,去做其他的题目了。

比赛结束了,小C的同学们都使用了$O(n2^n)$的算法通过了此题,小C却TLE了,但他觉得自己的算法应该是可以通过的。他想找到使得自己算法状态数最大的$G$,但是他太菜了,于是他向你求助。每次小C会给定一个数$n$,他想让你构造一个点数等于$n$的图$G$,使得小C的算法中合法状态数最大,并告诉他最大的状态数是多少。

由于小C会使用组合数对答案进行合并,因此你需要保证将图$G$中的边看成无向边之后,图$G$是连通的,这样小C的算法才会无机可乘。

由于小C很懒,因此他希望在方案数最多的条件之下,$G$中的边数还是最少的。

由于图$G$已知是由“好的”无向图变换而成,因此你只需要给小C一个带标号的“好的”无向图即可。如果有多种方案,输出任意一种即可。

题目描述

对于一张$n$个点,$m$条边,有标号,无自环无重边无孤点的无向图,定义它的变换是构造方式如下的有向图:

1.有向图有$m$个点,与无向图$m$条边一一对应。

2.对于无向图中每个点,将与它相连的边按照另一个端点从小到大排序,按顺序将这些边在有向图中的对应点连成一条链。

定义有向图$G$的一个状态为给每个点分配$0,1,2$之一的值,给每条边分配一个$0,1$之一的值。

定义一个状态合法当且仅当对于每个点下面五个条件均不满足

1.这个点值为$0$且它的入边和出边值不全为$0$。

2.这个点值为$2$且它的入边和出边值不全为$1$。

3.这个点入度为$2$,且这个点入边值之和不等于这个点的值。

4.这个点出度为$2$,且这个点出边值之和不等于这个点的值。

5.这个点的出边所能到达的点值不全都小于等于这个点的值。

现在请你构造一个点数为$n$的有向图$G$,满足下面几个条件:

1.$G$能被某个有标号无自环无重边无孤点的无向图变换而来。

2.$G$中的边都看成无向边之后$G$连通,即$G$是弱连通的。

3.$G$的合法状态数尽量的多。

4.在满足3的条件下,$G$的边数尽量小。

每次给定$n$,输出满足条件的任意一种图以及它的合法状态数。

输出图时只需要输出变换之前的无向图即可。

输入格式

一行一个正整数表示$G$的点数$n$。

输出格式

第一行一个正整数,表示小C的算法状态数最大值。

第二行一个正整数$n'(n'\geq 0)$表示你所输出无向图的点数。

接下来$n$行,每行两个正整数$u,v(u,v\in \{1,2,...,n'\})$表示无向图中一条连接$u,v$的边。

如果你输出的状态数最大值是正确的,且你输出了一张“好的”无向图(可能无法变换为最优的$G$),符合题目格式。你将会获得该测试点$40\%$的分数。

除去答案正确以及上面这种情况,其他的情况将会被判为答案错误。

样例输入

3

样例输出

13
4
1 2
1 3
3 4

样例解释

将三条边按顺序标号为$1,2,3$,然后进行变换,得到图$G$如下:

将边$(1,2)$,$(2,3)$分别编号为$1$,$2$,那么13种状态分别为:

1:三个点经过次数分别为$0,0,0$,未经过第一条边,未经过第二条边。

2:三个点经过次数分别为$1,0,0$,未经过第一条边,未经过第二条边。

3:三个点经过次数分别为$1,1,0$,未经过第一条边,未经过第二条边。

4:三个点经过次数分别为$1,1,0$,经过第一条边,未经过第二条边。

5:三个点经过次数分别为$2,1,0$,经过第一条边,未经过第二条边。

6:三个点经过次数分别为$1,1,1$,未经过第一条边,未经过第二条边。

7:三个点经过次数分别为$1,1,1$,经过第一条边,未经过第二条边。

8:三个点经过次数分别为$1,1,1$,未经过第一条边,经过第二条边。

9:三个点经过次数分别为$1,1,1$,经过第一条边,经过第二条边。

10:三个点经过次数分别为$2,1,1$,经过第一条边,未经过第二条边。

11:三个点经过次数分别为$2,1,1$,经过第一条边,经过第二条边。

12:三个点经过次数分别为$2,2,1$,经过第一条边,经过第二条边。

13:三个点经过次数分别为$2,2,2$,经过第一条边,经过第二条边。

可以证明,这样的图$G$状态数是点数为$3$的所有可能中本质不同的合法状态数最大的。

限制与约定

测试点编号 $n=$ 测试点编号 $n=$
$1$ $3$ $11$ $75$
$2$ $5$ $12$ $100$
$3$ $7$ $13$ $150$
$4$ $8$ $14$ $200$
$5$ $9$ $15$ $250$
$6$ $10$ $16$ $300$
$7$ $11$ $17$ $325$
$8$ $15$ $18$ $350$
$9$ $20$ $19$ $375$
$10$ $50$ $20$ $400$

时间限制:$1s$

空间限制:$512MB$