问题 4353 --选举

4353: 选举

时间限制: 1 Sec  内存限制: 128 MB
提交: 30  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

一场选举有三位选手分别编号为1,2,3,还有两位评委4,5。 评委打分时会给出一个{1,2,3}的排列,表示评委对选手的喜爱程度。例如评 委给出一个排列{2,1,3},表示最喜欢2,其次是1,最后是3。 两位评委将分别给出排列x、y。你需要做的是综合考虑x、y,给出一个最 终的排名z。 由于事先不知道x、y,所以你需要对于每一种不同的x、y,都提前设计好 相应的z。(显然x、y有36种情况) 正式地,你需要设计一个映射{X,Y}-->{Z},其中定义域是评委的排列,值 域是你给出的最终排列。(定义域大小是 36,值域大小是 6,所以映射数量是 6^36)。为了方便,用z=f(x,y)表示评委打分是x,y时最终排名是z。 如果随便给一个映射,可能会被喷,比如两个评委都最喜欢1,你最后却把 1 排在最后。为了避免这种情况,你的映射可能需要满足几个条件: 

 一致性:对于选手a,b,如果两个评委都更喜欢a,那么最终排名中a应当排 在b前面。 

 独立性:定义函数I(x,a,b),如果排列x中a的位置比b靠前,那么I(x,a,b)=1. 否则I(x,a,b)=0。对于选手 a,b,考虑评委打分的两种情况(x1,y1)和(x2,y2),如果 I(x1,a,b)=I(x2,a,b),并且 I(y1,a,b)=I(y2,a,b),那么 f(x1,y1)和 f(x2,y2)应当满足 I(f(x1,y1),a,b)=I(f(x2,y2),a,b)。 

 非独裁:如果对于任意的排列x,y,f(x,y)=x,那么称评委4独裁。如果对于 任意的x,y,f(x,y)=y,那么称评委5独裁。非独裁就是两个评委都不独裁。

输入

一个数m

输出

一行一个数 

 如果m=1,输出共有多少种映射方案(正如题目中所说,方案数是6^36)。 

如果m=2,输出有多少方案满足一致性。 

如果m=3,输出有多少方案满足独立性。 如果m=4,输出有多少方案满足一致性、独立性。 如果m=5,输出有多少方案满足一致性、独立性、非独裁。 

样例输入

1

样例输出

10314424798490535546171949056

提示

共5个测试点

来源

[提交][状态]