0.前言
也是被我同学鄙视了好吧!!!
那么,从今天开始,我要认真学数学了。最近数学社团在讲 sigmasigmasigma,那就写一篇关于 sigmasigmasigma 的介绍吧。
1.SIGMA的由来
sigmasigmasigma(表示为 ΣΣΣ)是希腊字母表中的第 181818 个字母,在数学中被用来表示 “求和”。
想象一下,如果要计算 1+2+3+4+51+2+3+4+51+2+3+4+5,虽然不难,但如果要计算 1+2+3+……+10001+2+3+……+10001+2+3+……+1000,逐个书写就太麻烦了。这时,sigmasigmasigma 符号就能派上大用场,用它可以把长长的加法算式浓缩成一个简洁的表达式。
2.SIGMA的理解
在写法上的理解
sigmasigmasigma 的基本写法是:∑i=abf(i)\sum_{i=a}^{b} f(i)∑i=ab f(i),其中:
ΣΣΣ是 $igma $ 符号,代表 “总和”;
iii 是求和变量,也叫 “索引”,可以是任何字母,常见的有 i,j,ki,j,ki,j,k等;
aaa 是下限,表示求和开始时变量的值;
bbb 是上限,表示求和结束时变量的值;
f(i)f(i)f(i)是求和表达式,表示每个项的计算规则。
整个表达式的意思是:当变量 iii 从 aaa 开始,每次增加 111,一直到 bbb 时,将所有f(i)f(i)f(i)的值加起来。
在C++中的理解
我们可以把 sigmasigmasigma 函数当作 forforfor循环,进行一系列累计,具体见下面的代码。
3.SIGMA的用法
基本用法:简单数列求和
最基础的 sigmasigmasigma 用法是计算连续整数的和。例如,∑i=15i\sum_{i=1}^{5} i∑i=15 i,这里下限 a=1a=1a=1,上限 b=5b=5b=5,表达式f(i)=if(i)=if(i)=i,它表示的就是 1+2+3+4+5,计算结果为 15。
再比如,∑k=36k\sum_{k=3}^{6} k∑k=36 k,就是 3+4+5+63+4+5+63+4+5+6,结果是 181818。
表达式含常数的求和
当求和表达式中出现常数时,计算方法也很简单。比如 ∑i=143\sum_{i=1}^{4} 3∑i=14 3,表示有 444 个 333 相加,即3+3+3+3=123+3+3+3=123+3+3+3=12。这里可以总结出一个规律:∑i=abc=c×(b−a+1)\sum_{i=a}^{b} c = c \times (b - a + 1)∑i=ab c=c×(b−a+1),其中 ccc是常数,(b−a+1)(b−a+1)(b−a+1)是项数。
表达式含变量倍数的求和
如果表达式是变量的倍数,如∑i=132i\sum_{i=1}^{3} 2i∑i=13 2i,它表示的是 2×1+2×2+2×3=2+4+6=122×1 + 2×2 + 2×3 = 2 + 4 + 6 = 122×1+2×2+2×3=2+4+6=12。也可以把倍数提到 sigmasigmasigma 外面,即2×∑i=13i=2×(1+2+3)=2×6=122\times\sum_{i=1}^{3} i = 2\times(1 + 2 + 3)=2\times6=122×∑i=13 i=2×(1+2+3)=2×6=12,结果是一样的。
多个表达式的求和
当 sigmasigmasigma 的表达式是多个项的和或差时,可以拆分成多个 sigmasigmasigma 的和或差。例如∑i=12(i+2i2)\sum_{i=1}^{2} (i + 2i^2)∑i=12 (i+2i2),可以拆分为∑i=12i+∑i=122i2\sum_{i=1}^{2} i + \sum_{i=1}^{2} 2i^2∑i=12 i+∑i=12 2i2。
先计算∑i=12i=1+2=3\sum_{i=1}^{2} i = 1 + 2 = 3∑i=12 i=1+2=3;再计算 ∑i=122i2=2×12+2×22=2+8=10\sum_{i=1}^{2} 2i^2 = 2×1^2 + 2×2^2 = 2 + 8 = 10∑i=12 2i2=2×12+2×22=2+8=10;最后相加得 3+10=133 + 10 = 133+10=13,和直接计算 (1+2×12)+(2+2×22)=(1+2)+(2+8)=3+10=13(1 + 2×1²)+(2 + 2×2²)= (1 + 2)+(2 + 8)=3 +
10=13(1+2×12)+(2+2×22)=(1+2)+(2+8)=3+10=13结果一致。
进阶用法:双重 SIGMA 求和
双重 sigmasigmasigma 是指存在两个求和变量的情况,形如∑i=ab∑j=cdf(i,j)\sum_{i=a}^{b}\sum_{j=c}^{d}f(i,j)∑i=ab ∑j=cd f(i,j),表示先固定 iii 的值,对 jjj 从 ccc 到 ddd 的所有 f(i,j)f (i,j)f(i,j) 求和,再将得到的结果对 iii 从 aaa 到$ bbb 求和。
例如∑i=12∑j=12(i+j)\sum_{i=1}^{2}\sum_{j=1}^{2}(i + j)∑i=12 ∑j=12 (i+j),先计算 i=1i=1i=1 时,jjj 从 111 到 222 的和:(1+1)+(1+2)=2+3=5(1+1)+(1+2)=2+3=5(1+1)+(1+2)=2+3=5;再计算 i=2i=2i=2 时,jjj 从 111 到 222 的和:(2+1)+(2+2)=3+4=7(2+1)+(2+2)=3+4=7(2+1)+(2+2)=3+4=7;最后将两个结果相加,5+7=125+7=125+7=12。
变量步长不为 1 的求和
之前我们接触的求和变量都是每次增加 1,其实变量的步长可以是其他数值。比如∑i=1i+=25i\sum_{\substack{i=1 \\ i+=2}}^{5}i∑i=1i+=2 5 i,这里 iii 从 111 开始,每次增加 222,到 555 结束,它表示的是 1+3+5=91+3+5=91+3+5=9。
含分式的求和
当表达式中含有分式时,计算过程稍显复杂,但原理不变。例如∑i=13ii****um_{i=1}^{3}\frac{i}{i + 1}∑i=13 i+1i ,分别计算每一项:
i=1i=1i=1时,11+1=12\frac{1}{1+1}=\frac{1}{2}1+11 =21
i=2i=2i=2时,22+1=23\frac{2}{2+1}=\frac{2}{3}2+12 =32
i=3i=3i=3时,33+1=34\frac{3}{3+1}=\frac{3}{4}3+13 =43
求和,12+23+34=612+812+912=2312\frac{1}{2}+\frac{2}{3}+\frac{3}{4}=\frac{6}{12}+\frac{8}{12}+\frac{9}{12}=\frac{23}{12}21 +32 +43 =126 +128 +129 =1223 .
4.SIGMA在C++中的例题
题目传送门
题目描述
给定一个长度为 NNN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)A=(A1 ,A2 ,…,AN )。定义 f(l,r)f(l,r)f(l,r) 如下:
* f(l,r)f(l,r)f(l,r) 表示区间 (Al,Al+1,…,Ar−1,Ar)(A_l,A_{l+1},\ldots,A_{r-1},A_{r})(Al ,Al+1 ,…,Ar−1 ,Ar ) 中不同数的个数。
请计算下式的值:
∑i=1N∑j=iNf(i,j)\sum_{i=1}^{N}\sum_{j=i}^N f(i,j) i=1∑N j=i∑N f(i,j)
输入格式
输入以如下格式从标准输入中给出。
> NNN A1A_1A1 A2A_2A2 …\ldots… ANA_NAN
输出格式
请输出答案。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
限制条件
* 1≤N≤2×1051\leq N\leq 2\times 10^51≤N≤2×105
* 1≤Ai≤N1\leq A_i\leq N1≤Ai ≤N
* 输入的所有数均为整数
样例解释 1
以 f(1,2)f(1,2)f(1,2) 为例,(A1,A2)=(1,2)(A_1,A_2)=(1,2)(A1 ,A2 )=(1,2),其中不同的数有 222 个,所以 f(1,2)=2f(1,2)=2f(1,2)=2。再看 f(2,3)f(2,3)f(2,3),(A2,A3)=(2,2)(A_2,A_3)=(2,2)(A2 ,A3 )=(2,2),其中不同的数有 111 个,所以 f(2,3)=1f(2,3)=1f(2,3)=1。fff 的总和为 888。
分析
ABC371E
对于每个区间,如果有重复的数,我们认为最早出现的那个数有贡献。
例如 1,2,3,4,1,4,51,2,3,4,1,4,51,2,3,4,1,4,5 中,第 1,2,3,4,71,2,3,4,71,2,3,4,7 个数对答案有贡献。
统计每个数对答案的贡献即可。
我们设 jjj 为满足 aj=aia_ j=a_iaj =ai 且 j<ij<ij<i 的最大值(若不存在为 000),那么aia_iai 的贡献就是 (i−j)×(n−i+1)(i−j)×(n−i+1)(i−j)×(n−i+1),其中 (i−j)(i−j)(i−j) 为左端点的可能数,(n−i+1)(n−i+1)(n−i+1) 为右端点的可能数。
5.完结撒花
@AC君 求加精
@洛谷:姚昕辰,看到没有!!!