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.

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

时间限制: 1 Sec 内存限制: 128 MB提交: 1 解决: 0

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

## 题目描述

## 输入

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
```