把直角的那个顶点放在原点，枚举其中一条边的横坐标，然后勾股定理得到纵坐标。旋转90度得到另外一个直角边的方向向量，伸缩到对应长度，看看是否整点。唯一的trick是除了直角边的那条边平行与坐标轴要注意。
令f[i][j]表示现在才在i上，i上的次数是奇数，其它位置都是偶数的情况下，从i走到j所需要的步数。
f[i][j] = f[i][j-1] + f[a[j-1]][j-1] + 2
记忆化递归求解f[0][n]即可。
先考虑单次操作的情况，f[i][0] = C[k + i – L][k] = 要求的答案。
对这个f[i][0]做一次差分，那么f[i][1] = f[i + 1][0] – f[i][0]，可以看做这是i处的导数。
然后f[i][2]视为对f[i][1]这个数列作差分，一直往上。
然后由于C[m][n] = C[m – 1][n] + C[m – 1][n – 1]，所以你会发现f[i][j] = C[k + i – L][k – j]。
那么现在变换一下f的递推关系得到f[i + 1][j] = f[i][j] + f[i][j + 1]。
也就是说，如果我知道到第i个数字的各阶导数，那么我可以一个一个数字往后推，得到其它数字以及他们的各阶导数。
又因为f[i][j] = C[k + i – L][k – j]，k不超过100，所以j只要算到100阶就行了，再高后面的都是0。
由于这个递推式里面是加法，和答案里的求和相吻合，所有可以把各个询问叠在一起往后加着算。
于是得到这么一个算法，对于每个询问，求出他在l处的各阶导数，放进f[l][0..k]里面，在r出也求出各阶导数，放到f[r][0..k]里面(这里是为了抵消，用减法放进去)。
最后，大家一起从前往后推就好了。
令f[i][j][k]表示第i行到第j行这个子矩阵里，左边界选择第k列，右边界最远能到第几列。
首先f[i][j][k] ≤ min(f[i][j – 1][k], f[i + 1][j][k], f[i][j][k + 1])
除了这几个限制外，可能产生新冲突的就只可能是”第i行k列和第j行k列上的元素”与”第i行后面的元素和第j列后面的元素”。
那么按j – i的大小枚举i, j，再倒着枚举k，就可以用一个桶记录每个元素在第i行以及第j行最前出现的列是多少。
这样就可以处理掉这两个元素产生的冲突。
桶的清空稍微用一些编码技巧，就能O(n^3)写过去。