UOJ Logo Universal Online Judge

UOJ

#95. 【集训队互测2015】胡策的数列

统计

在 OI 界,有一个无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!

今天胡策正在研究一个远古传下来的数列:$a_0, a_1, a_2, \dots$,数列的第 $k$ 项为 $a_k$。这个数列有特别的性质,对于 $i > 1$ 有:$25 a_i + 20 a_{i - 1} = 12 a_{i - 2}$。因为流传的时间太过久远,$a_0$ 和 $a_1$ 的值都已经看不清了,但是在最后还记载着,这个数列有一个特别的性质:对于任意的 $i \geq 0$,都有 $a_i \geq 0$。

然而胡策已经看穿了一切:对于任意一个正数 $t$,满足 $a_0 = t$ 的数列 $a$ 是唯一的!但是,他想拿这个问题考一考拜胡策为师的你。

具体来说,胡策会给你一个长度为 $n$ 的表格,一开始每个格子都写着 $0$。有时他会让你将 $a_0 = t$ 时的数列 $a$ 从第 $p$ 项到第 $p + r - l$ 项的值分别写入表格中第 $l$ 到第 $r$ 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。

当然,作为胡策的弟子,你必须在胡策提出一个询问的时候马上作出回应。

因为这是一个远古的问题,胡策只给了你一台远古的计算机,它只有 $64\texttt{MB}$的内存。

输入格式

第一行两个正整数 $n,m$。分别表示表格的长度和操作个数。

接下来 $m$ 行,每行描述一个操作。每行的第一个整数 $\mathrm{type}$ 描述了操作的类型,$\mathrm{type} = 1$ 表示是修改操作,$\mathrm{type} = 2$ 表示是询问操作。

如果是修改操作,接下来有四个整数 $l,r,t,p$,意义如上所述。

如果是询问操作,接下来有两个整数 $l,r$,意义如上所述。

由于胡策需要确定你是在线回答他的问题,输入中的 $l, r$ 是加密了的。于是你需要把输入中的 $l, r$ 分别异或 $\mathrm{lastans}$ 来得到实际的 $l, r$。$\mathrm{lastans}$ 表示上一次询问操作的答案,初始为 $0$。保证实际的 $l, r$ 满足 $1 \leq l \leq r \leq n$。

输出格式

对每个询问操作输出一行,表示询问的答案。

答案一定能写成 $\frac{v}{u}$ 的形式,其中 $v, u$ 是互质的整数,且 $u > 0$。为了避免分数,你只用输出一个介于 $0$ 到 $10^9 + 8$ 之间的整数 $x$ 满足 $ux \equiv v \pmod{10^9 + 9}$ 来表示答案。显然在本题中,这样的 $x$ 是唯一的。

样例一

input

3 3
1 1 3 2 3
1 2 2 4 5
2 1 3

output

867840008

explanation

答案是 $\frac{592}{3125}$,对应的 $x$ 为 $867840008$。

样例二

input

1000000000 3
1 1 12450 6666666 23333333
1 6666 99999 2333 44444
2 1 1000000000

output

431287288

样例三

见样例数据下载。

限制与约定

对于 20% 的数据,$n,m \leq 1000$。

对于 50% 的数据,$n,m \leq 30000$。

对于 100% 的数据,$1 \leq n \leq 10^9$,$1 \leq m \leq 10^5$,$1 \leq t \leq 10^9$,$1 \leq p \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$64\texttt{MB}$

来源

中国国家集训队互测2015 - By 张天扬

下载

样例数据下载