2019.5.26

Veröffentlicht am

Life is ten percent what you make it and ninety percent how to take it.

Nephren Ruq Insania

对于区间$[l,r]$， 查询 ，一直到 $ a_r $
请注意每次的模数不同。

输入输出格式
输入格式：
第一行两个整数$n,m$,表示序列长度和操作数。
接下来一行，$n$个整数$a_i$表示这个序列。
接下来$m$行，可能是以下两种操作之一：

1 l,r,x，表示区间$[l,r]$加上$x$

2 l,r,p ,表示进行一次法咒共鸣，模数为$p$

输出格式：
对于每个操作2，输出一行表示答案。
输入输出样例

输入样例#1：
6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

输出样例#1：
1
3
1

输入样例#2：
5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417

输出样例#2：
4306230
697527

说明

测试点　　　
n的范围　　　　
m的范围　　　　
特殊限制

1
$n = 5 $
$m = 5 $
$a_i \le 3$

2
$n = 1000 $
$m = 1000 $
查询区间长度为1

3
$n = 100000$
$m = 100000$
查询区间长度为1

4
$n = 1000 $
$m = 1000 $
查询区间长度不大于2

5
$n = 100000$
$m = 100000$
查询区间长度不大于2

6
$n = 1000 $
$m = 1000 $
$a_i \le 2$

7
$n = 1000 $
$m = 1000 $
$p = 2$

8
$n = 100000$
$m = 100000$
$p = 2$ 无修改

9
$n = 1000 $
$m = 1000 $
$p \le 100000$ 无修改

10
$n = 500000$
$m = 500000$
无

对于100%的数据，$n , m \le 500000$ , 序列中每个数在$[1,2\cdot 10^9]$内，$p \le 2 \cdot 10^7 $, 每次加上的数在$[0,2\cdot 10^9]$内

题解

1过不了挺难的。

2，3区间长度为1只需要一个LL区间加线段树即可。

4，5只需要查两次，然后快速幂。实力送分

6也很简单，如果题意指$a_i$始终小于等于2的话。只需要查询区间中有没有0，有几个2，快速幂一下

想到了一个$O(Nlog^3N)$的做法关于定模数。

用一颗线段树来维护，每次pushup维护$V_L^{V_R}$

区间加会被拆成$O(logn)$个区间，每个区间向上有$O(logn)$个区间，然后每个区间$pushup$需要$O(logn)$的复杂度（快速幂）。查询同样是把右边区间维护的值作为左边的指数。

这样做可能勉强能过#7，8？？

这就有80了。。。

哦对了#9直接暴力即可，所以有90了。。（第#9个点的意义在何。？难道n,m不应该大一点吗）

Emmm不过#10不好想啊。

不过看到模数$2e7$就知道肯定和欧拉函数与欧拉定理有关。

假如暴力递归降幂好像没什么优化。

【模板】欧拉定理

题目背景

模板题，无背景

题目描述

给你三个正整数，$a,m,b$,你需要求：
$a^b \mod m$

输入输出格式

输入格式：
一行三个整数，$a,m,b$
输出格式：
一个整数表示答案
输入输出样例

输入样例#1：
2 7 4

输出样例#1：
2

输入样例#2：
998244353 12345 98765472103312450233333333333

输出样例#2：
5333

说明
注意输入格式，$a,m,b$ 依次代表的是底数、模数和次数
样例1解释：
$2^4 \mod 7 = 2$
输出2
数据范围：
对于全部数据：
$1≤a≤10^9$
$1≤b≤10^{20000000}$
$1≤m≤10^6$

题解

$a^b = a^{b\mod \varphi(m) + \varphi(m)} , b > \varphi(m)$

注意必须大于才能用。

这定理根本不会证明，所以就当写着玩吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
int a , b , m , pm , flag;

inline void Mod(int& x){
	if(x >= pm) x %= pm , flag = 1;
}
inline int read()
{
	char ch = getchar();
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch <= '9' && ch >= '0')
		b = b * 10 + ch - 48 , Mod(b) , ch = getchar();
	return b;
}

inline int pow(int x, int y)
{
	int ans = 1 , base = x % m;
	for( ; y ; y >>= 1 , base = 1ll * base * base % m)
		if(y & 1)
			ans = 1ll * ans * base % m ;
	return ans;
}

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd( y, x % y);
}

inline void getpm(int mod)
{
	for(int i = 1 ; i < mod ; ++i)
		if(gcd(i , mod) == 1)
			++pm;
	return;
}

int main()
{
	scanf("%d%d",&a,&m);
	getpm(m);
	if(m == 1){
		puts("0");
		return 0;
	}
	read();
	if(!flag){
		printf("%d\n",pow(a,b));
		return 0;
	}

	printf("%d\n",pow(a,b + pm));
}

了解一个黑科技，低于线性复杂度求阶乘。

【模板】快速阶乘算法

题意

$n! \mod p$

数据范围

$n,p \leq 2^{31}-1$

题解

$O(\sqrt{n}log^2n)$的解法
让我们来看看这道题要求我们做什么:计算$n! \mod P$
那么一个简单粗暴的思路是分块,我们希望计算$1 \dots n$的乘积，我们将序列分成长度为$B$的若干个块，如果我们能快速求出每个块的积，我们就能凑出n阶乘来
那具体来讲我构造这样的一个多项式$f(x)$

如果我们能求出$f(0),f(B),f(2B) \dots f(\lfloor \frac{n}{B} \rfloor B)$的话，我们就能在$O(\lfloor \frac{n}{B}\rfloor+B)$的时间内计算出答案了
使用多项式多点求值就可以在$O(\sqrt{N}log^2n)$的时间内计算出答案来
$O(\sqrt{n}logn)$的做法
上面的做法可以通过玄学调整块长来优化常数，但是一个log做法只能求出$f(0),f(B) \dots f(B^2)$的值，因此我们需要把块长设为$\sqrt{n}$
我们发现我们只需要求出f这个多项式的一些点值就可以生成答案了，那么我们可以尝试不求出$f$的系数表达，而是直接使用f的点值进行迭代
为了让我们能够转移，我们将f的定义从一维的情况拓展到二维,我们定义这样一个多项式出来

那么我们最后要求的是$f(B,0),f(B,B) \dots f(B,B^2)$这些点值
一个显而易见的性质是,已知多项式f的$n+1$对点值$(x,f(x))$就可以唯一确定这个多项式，因此如果我们求出了$f(d,0),f(d,B) \dots f(d,dB)$我们就可以唯一的确定多项式$f(d,x)$了
现在我们尝试在d这一位上做倍增
具体来讲我们需要实现这两件事情
已知

求出

通过这个操作我们可以把d乘2
已知

求出

通过这个操作我们可以把$d$加$1$
然后有了这两个操作之后使用一个类似于快速幂的做法,我们迭代log轮就可以把求出$f(B,0),f(B,B) \dots f(B,B^2)$了
那么我们考虑如何实现这两个过程
将d乘2
我们知道$f(2d,x)=f(d,x)f(d,dx)$
因此我们只需要求出来

和

就能计算出我们想要的点值序列的
那么我们不妨构造一个新的多项式$h(x)=f(d,Bx)$
那么我们需要解决这样一个问题
已知

希望求出

求出上面的东西之后我们就已知了

只要求出

我们就可以把倍增需要的两个序列求出来了
所以总结一下就是已知

希望求解

也就是说我们希望从点值转移到点值，那么我们学过的算法里面只有拉格朗日插值是一个完全不涉及多项式的系数还能算多项式的点值的算法
因此我们尝试使用拉格朗日插值算法

我们将$\prod$里的分子提出来就是

这里说明一下为什么$\Delta+n-i$不可能是0，因为$h(x)$本质上代表了一段连续数字的乘积，而根据我们算法的原理，$h(\Delta+n)$和$h(i)$一定代表了两段不同的数字，所以分母不可能为0
然后考虑$\prod_{j \neq }\frac{1}{i-j}$手玩一下会发现他是两段阶乘乘起来的,所以式子可以化成这样

如果我们设一些这样的函数出来

那么我们就可以得到这样的式子

这东西当然是个标准卷积式子,把$f$和$g$求出来卷一卷就行了
知道了$h’(n+k)$之后我们就可以推出$h(n)$来了,发现$h’(n+k)$和$h(n)$的比值是一段区间当中数字的乘积，这个系数在可以$two-pointer$扫一遍在$O(k+logP)$的时间内求出
(这里直接求逆元是$O(klogP)$的，但是的确存在$O(k+logP)$的算法)
这样我们就可以成功的求出倍增需要的两个数组，于是就可以实现把$d$乘2的操作了
迭代一次是$O(nlogn)$的
将d加1
现在已知

希望求出

显然$f(d+1,(d+1)B)$暴力计算就行了
对于剩下的项，我们可以用这个式子计算

显然迭代一次是$O(n)$的
完成了这两个操作之后我们就可以在$log$轮迭代中把d从0迭代到B了
然后我们乘一乘就能把阶乘算出来啦~
时间复杂度