Codeforces 765D Artsem and Saunders

Codeforces 765D Artsem and Saunders

题目链接

http://codeforces.com/problemset/problem/765/D

题目大意

给你一个函数 $f(x)$ ,让你求出两个函数 $g(x)$ 和 $h(x)$ 使得 $g(h(x)) = x$ 和 $h(g(x)) = f(x)$ 成立,对于 $f(x)$ 和 $g(x)$ , $x$ 的定义域为 $1$ 到 $n$ ,对于 $h(x)$ 定义域为 $1$ 到 $m$

你需要求出全部的 $g(x)$ 和 $h(x)$ 以及 $m$ ,无解输出 $-1$

题目分析

可观察得到三个式子

$$g(h(g(x))) = g(x) = g(f(x))$$

$$h(g(h(x))) = f(h(x)) = h(x)$$

$$h(g(h(g(x)))) = f(x) = f(f(x))$$

所以由第三个式子可知必有 $f(x) = f(f(x))$ 时才有解

由第二个式子可知 $h(x)$ 里的元素是 $x = f(x)$ 构成的

$m$ 就是 $x=f(x)$ 的个数

在通过第一个式子确定 $g(x)$ 的值

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up