Permutation

permutation.cpp/in/out
Time limit: 1s
Memory limit: 512MB

定义一个长度为 n 的排列 p 的生成图为一个 n 个点 n 条边的有向图,且该有向图的第 i 条边
为 i 指向 pi 的有向边
由于排列的定义,该图每个点的入度与出度皆为 1,故这个图一定是由许多环组成,如果所有
环的长度皆为偶数,那么我们称这个排列为好的
本来出题人想问你有多少个长度为 n 的好的排列,但是目前排列 p 的部分数字已经被中央钦
定了,请你求出在这个条件下还有多少个好的排列,答案对 998244353 取模

 

第一行一个正整数 n
第二行 n 个数字,第 i 个数字如果为 0 则表示中央没有钦定 pi 等于几,否则 pi 就被钦定成这
个数啦

 

一行一个整数,表示答案

1.in

6
0 0 0 0 0 0

1.out

225

2.in:

6
2 0 0 0 0 0

2.out:

45

 

直接说满分做法吧。

首先可以发现,对于被钦定得点,他被更改以后更改得只有大小这个信息有价值,即改变了内部边数得奇偶性。

可以把奇数个点看成一个点,因为可以考虑其中得边数刚好有偶数条。(偶数同理)

我们记录他们得数量并将其表示为二元组(x,y)

考虑先处理掉偶数链,

1.偶数链可以偶数链组合成一个新的偶数链.

即(x,y) -> (x-1,y)

2.偶数链和一个奇数链组合成一个新的偶数链.

即(x,y) - >(x-1,y)

发现结果相同,那么直接就是对于任意一个偶数链,

若先考虑更改这个偶数链,那么他可以连向自己,连向其他偶数链,连向奇数链,总共有(x+y)种方案,

然后可以一直处理掉所有得x。

结束以后新的二元组为(0,y)

考虑奇数链,他只能和一个奇数链组成一个偶数链,有y-1种方案。

即(0,y) - >(1,y-2)

然后不停处理就好了。

继续发现题目里面可能有奇数环,此时返还0即可。

或者如果有奇数个奇数链,也一定不可能组合出合法方案,返回0即可.

搞定

 

c++代码如下:

 

2018年1月10日 0 / /
Tag:  No Tags

5 + 6 =