NOIP 模拟赛第六场

预估分数：\(100+100+70+10\)，实际分数 \(100+100+70+10\)，排名 \(1/10\)。

笑点解析就是 T3 T4 除了我之外无一人得分，所以拉开了第二名 \(80\) 分，还是可喜可贺的。特别是 T3，我在看错题的情况下分数反而得到的更高，我会放在后面讲。

T1

题目大意：我们定义函数 \(\text{f}(x,y)\) 如下：

  • 若 \(x = y\)，其值为 \(1\)；

  • 若 \(x \neq y\)，其值为 \(\text{f}(x + y - |x - y|,|x - y|) + 1\)，特别地，若出现无限循环，则 \(\text{f}(x,y) = 0\)。

现在给定一个长度为 \(n\) 的排列 \(a\)，\(q\) 次询问，每次给出两个整数 \(l,r\)，求 \(\sum_{i=l}^r\sum_{j=i + 1}^r \text{f}(a_i,a_j)\) 的值。

思路分析：推式子好题。难度应该能到下位青。

首先我们先推一下 \(\text{f}(x,y)\) 能产生贡献需要满足什么条件。

首先因为是排列所以初始 \(x\) 肯定不等于 \(y\)。我们令 \(x > y\)，则改变之后会变成 \(\text{f}(x + y - |x - y|,|x - y|) = \text{f}(2y,x - y)\) 。