cstdio现有一个长度为N的序列{X1,X2,...,XN}，要求支持两种操作：
1. 0 l r 表示将[l, r]范围内的$X_i$变为${X_i}^2 \mod p $.
2. 1 l r 询问$\sum_{i = l}^r X_i$.
| 题目名称 | 1370. [thusc2015]平方运算 |
|---|---|
| 输入输出 | thusc2015_square.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 Asm.Def
于2015-06-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：34， 通过率：41.18% | ||||
 FoolMike |
100 | 5.173 s | 13.28 MiB | C++ |
 bbsh |
100 | 5.476 s | 195.64 MiB | C++ |
 SliverN |
100 | 5.625 s | 13.88 MiB | C++ |
 Asm.Def |
100 | 7.539 s | 115.60 MiB | C++ |
 ZXCVBNM_1 |
100 | 10.431 s | 11.06 MiB | C++ |
 2bx |
100 | 11.191 s | 5.65 MiB | C++ |
 thomount |
100 | 12.261 s | 109.13 MiB | C++ |
 stdafx.h |
100 | 12.332 s | 5.74 MiB | C++ |
|
stdafx.h |
100 | 12.380 s | 5.74 MiB | C++ |
|
stdafx.h |
100 | 12.438 s | 5.09 MiB | C++ |
| 关于 平方运算 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Asm.Def :
跪万古夹心神犇，考场上看出了这题神奇的性质。 性质：每个数按照f(x)=x*x%p这样移动是有环的，且环大小的lcm值非常小，而且进入环所需次数也很小。 所以线段树上维护下按环走一周的答案就行了，不是环的部分直接暴力，按势摊还后显然正确。 时间复杂度大概是O(nlogn*C+n*logp)，C是环长的lcm，写个程序算算发现很小的，也就100以下，所以就随便跑了…… | ||||
|
回复 @cstdio :
= =考场上都没看题怎么可能会算法呢…… Asm.Def
2015-06-08 08:34
3楼
| ||||
|
回复 @Asm.Def :
Orzzzzzzzzzzzzzz给考场上会算法的跪傻 | ||||
|
自己弱不能怪社会= =考场上调试不出就是不会做= =
| ||||
1370. [thusc2015]平方运算
★★★☆ 输入文件：thusc2015_square.in
输出文件：thusc2015_square.out
简单对比时间限制：3 s 内存限制：512 MiB
Description
Input
第一行有三个整数N，M，p，分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。
接下来一行N个数代表一开始的序列{X1,X2,...,XN}。
接下来M行，每行三个整数op,l,r。其中op代表本次操作的类型。若op=0，代表这是一次平方操作，平方的区间为[l,r]；如果op=1，代表这是一次询问操作，询问的区间为[l,r]。
Output
对于每次的询问操作，输出一行代表这段区间内数的总和。注意：答案没有对任何数取模。
Sample Input
3 3 11
1 2 3
1 1 3
0 1 3
1 1 3
1 2 3
1 1 3
0 1 3
1 1 3
Sample Output
6
14
14
HINT
对于100%的数据，∀i,Xi∈[0,p),l,r∈[1,n]
N，M，p的范围如下：
编号 N M p
1 1000 1000 233
2 1000 1000 2332
3 100000 100000 5
4 100000 100000 8192
5 100000 100000 23
6 100000 100000 45
7 100000 100000 37
8 55000 55000 4185
9 55000 55000 5850
10 55000 55000 2975
11 55000 55000 2542
12 55000 55000 2015
13 60000 60000 2003
14 65000 65000 2010
15 70000 70000 4593
16 75000 75000 4562
17 80000 80000 1034
18 85000 85000 5831
19 90000 90000 9905
20 100000 100000 9977