← 返回题目

题库练习 Matrix

← 上一题下一题 →

A9201 | $Matrix$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You have a string of decimal digits $s$ . Let's define $b_{ij}=s_{i}·s_{j}$ . Find in matrix $b$ the number of such rectangles that the sum $b_{ij}$ for all cells $(i,j)$ that are the elements of the rectangle equals $a$ in each rectangle. A rectangle in a matrix is a group of four integers $(x,y,z,t)$ $(x<=y,z<=t)$ . The elements of the rectangle are all cells $(i,j)$ such that $x<=i<=y,z<=j<=t$ .

输入格式

The first line contains integer $a$ ( $0<=a<=10^{9}$ ), the second line contains a string of decimal integers $s$ ( $1<=|s|<=4000$ ).

输出格式

Print a single integer — the answer to a problem. Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入 #1

10
12345

输出 #1

输入 #2

16
439873893693495623498263984765

输出 #2

C++ 编辑器

输入

输出