bzoj#P2449. 统计解个数

统计解个数

题目描述

给定函数 f(x)f(x) ,它在 [k,k+1][k,k+1] 上是线性的,xx 是整数时,f(x)f(x) 也是整数。即当 kk 是整数时,x[k,k+1]x\in [k,k+1]f(x)=(k+1x)f(k)+(xk)f(k+1)f(x)=(k+1-x)f(k)+(x-k)f(k+1)

f1(x)=f(x)f^1(x)=f(x)fn(x)=f(fn1(x))f^n(x)=f(f^{n-1}(x))。给出 f(0),f(1),,f(m)f(0),f(1),\dots,f(m),求 fn(x)=xf^n(x)=xx[0,m]x\in [0,m] 的解的个数。

输入格式

本题有多组数据,对于每组数据:

第一行读入一个整数 mm

第二行读入 m+1m+1 个整数,第 ii 个数表示 f(i1)f(i-1)

第三行读入两个整数 nnmodnummodnummodnummodnum 表示答案需要 modmodnum\bmod modnum

相邻两组数据中有一个空行。

最后以 00 结束。

输出格式

对于每组数据输出一行表示答案。如果有无穷多个输出 Infinity

2
2 0 2
2 10
3
0 1 3 2
1 137
3
2 3 0 3
20 10000
0
4
Infinity
9074

数据规模与约定

对于 100%100\% 的数据,1n5×1031\le n\le 5\times 10^31m801\le m \le80modnum104modnum\le 10^4

题目来源

2011 福建集训