D. 【GENOIP#45】nogirlfriend
1 s
256 MB
题目描述
你的朋友 ezoilearner 没有找到女朋友，于是他给了你一个长度为 $n$ 的数列 $s$ 。
你需要找出有多少个三元组 $(a,b,len)$ ，满足
- $1 \leq a \leq a+len-1$
- $\forall i \in [0,len-1] \ s_{a+i}-s_{a} = s_{b+i} - s_{b}$
输入格式
第一行一个正整数 $n$ 。
第二行 $n$ 个非负整数表示 $s$ 。
输出格式
一行一个整数表示答案。
样例 1
样例 2
数据范围与提示
所有 $len=1,a < b$ 的三元组都满足条件，共有 45 个。
满足条件的三元组还有 $(1,5,2),(1,8,2),(2,4,2),(3,7,2),(5,8,2)$ 。
更多样例请见下发文件。
数据范围和提示
| 子任务编号 | 分数 | $n\leqslant$ | $s_i\leqslant$ |
|---|---|---|---|
| $1$ | $8$ | $500$ | $1000$ |
| $2$ | $12$ | $2000$ | $10^9$ |
| $3$ | $12$ | $300000$ | $1$ |
| $4$ | $12$ | $300000$ | $2$ |
| $5$ | $20$ | $80000$ | $10^9$ |
| $6$ | $36$ | $300000$ | $10^9$ |
OI
Contest Ended