#CW49. 列竖式(column)

列竖式(column)

题目描述

给定三个长度相同的十进制数字串。对每一对下标 (i,j)(i, j)(1≤i≤j≤n1 \le i \le j \le n),取三个串的第 ii 位到第 jj 位,要求这三个片段在原位置对齐,并判断是否满足前两个片段之和等于第三个片段。所有片段都允许有前导零。请输出满足条件的下标对数量。

输入格式

从 column.in 文件读入数据。

输入共三行,依次给出三个长度均为 nn 的数字串。保证 1≤n≤1061 \le n \le 10^6。

输出格式

将结果输出到 column.out 文件。

输出一个整数,表示满足条件的区间数量。

样例 1 输入

037523
040834
978367

样例 1 输出

4

样例 1 解释

满足条件的四组下标为 (2,2)(2,2)、(2,4)(2,4)、(3,4)(3,4)、(6,6)(6,6)。例如 (2,4)(2,4):375+408=783375 + 408 = 783,与第三个串的第 22 到第 44 位对齐相等。

数据范围

所有输入字符都是十进制数字。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼41\sim 4 n≤50n \le 50
2 20 5∼85\sim 8 n≤2000n \le 2000
3 30 9∼149\sim 14 n≤105n \le 10^5
4 40 15∼2015\sim 20 n≤106n \le 10^6