QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[-4]

# 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很慌张,他看了一眼数据范围,n400,由于机房的电脑非常厉害,这个数据范围明显是状压dp了。虽然小C并不会,但他会记忆化搜索,他找到了一种做法:

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

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

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

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

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

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

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

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

比赛结束了,小C的同学们都使用了O(n2n)的算法通过了此题,小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(n0)表示你所输出无向图的点数。

接下来n行,每行两个正整数u,v(u,v{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