程序设计在线评测(Online Judge)

2017年湖南科技大学大学生计算机程序设计竞赛初定于12月17日举行!有意参赛请加QQ群“湖科大程序设计校赛群(369699377)”

问题 1058. -- 2010欧洲西南分区赛:Periodic points

1058: 2010欧洲西南分区赛:Periodic points

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

题目描述

Computing the number of xed points and, more generally, the number of periodic orbits within a dynamical
system is a question attracting interest from di erent elds of research. However, dynamics may turn out to
be very complicated to describe, even in seemingly simple models. In this task you will be asked to compute
the number of periodic points of period n of a piecewise linear map f mapping the real interval [0;m] into
itself. That is to say, given a map f : [0;m] ! [0;m] you have to calculate the number of solutions to the
equation fn(x) = x for x 2 [0;m], where fn is the result of iterating function f a total of n times, i.e.

输入

The input consists of several test cases, separated by single blank lines. Each test case begins with a line
containing the integer m (1  m  80). The following line describes the map f; it contains the m+1 integers
f(0); f(1); : : : ; f(m), each of them between 0 and m inclusive. The test case ends with a line containing two
integers separated by a blank space, n (1  n  5 000) and the modulus used to compute the result, mod
(2  mod  10 000).
The input will nish with a line containing 0.

输出

For each case, your program should output the number of solutions to the equation fn(x) = x in the
interval [0;m] modulo mod. If there are in nitely many solutions, print Infinity instead.

样例输入

2
2 0 2
2 10

3
0 1 3 2
1 137

3
2 3 0 3
20 10000

0

样例输出

4
Infinity
9074

提示

来源

[提交][状态][讨论版]