Codeforces 364 A Matrix 题解（矩形构造）

C. Matrix time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You have a string of decimal digits s. Let's define bij = si·sj. Find in matrix b the number of such rectangles that the sum bij 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.

Input

The first line contains integer a (0 ≤ a ≤ 109), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).

Output

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.

Examples input

10
12345




output
6




input
16
439873893693495623498263984765




output
40














题意：
	就是给你一个字符串s,矩阵B bij=si*sj; 问你b矩阵中的长方形里各个元素的和加起来等于a的有
多少个？



写写样例可以推出 长方形中各元素的和等于构成它长的元素之和*构成它宽的元素之和
	又由于行列相等,那么我们只需记录行所能产生的和有多少,然后去找到 s1*s2=a的 即可
我们去枚举行的可能的和,找到a的因子，由于行列相同我们就枚举行就可以了
注意当a==0时的判断
	因为除数不能为0 所以当a==0时 行为0的应该单独判断,再去枚举不为0的行的和,去找到列上的0
这一题主要理解，字符串s任意一个区间，作为行，任意一个区间作为列都可以组成一个小矩形，你把行跟列乘起来会发现可以提因子，最后矩形的和变成了构成它长的元素之和*构成它宽的元素之和，然后我们就可以枚举所有区间的和，最后ans += book[i]*book[a/i];同时最大就是4e4， 不用到1e9

数据范围 long long
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 4e4 + 5;
long long book[maxn];
char str[maxn];
int main()
{
    int a;
    cin >> a >> str;
    int len = strlen(str);
    for(int i = 0; i < len; i++)
    {
        int sum = 0;
        for(int j = i; j < len; j++)
        {
            sum += str[j]-'0';
            book[sum]++;
        }
    }
    long long ans = 0;
    if(a == 0)
    {
        for(int i = 1; i < maxn; i++)
            ans += book[i]*book[0]*2;
        if(book[0])
            ans += book[0]*book[0];  //这里不能*2
    }
    else
    {
        for(int i = 1; i < maxn; i++)
        {
            if(a/i >= maxn) continue;
            if(a%i == 0)
              ans += book[i]*book[a/i];
        }
    }
    cout << ans << endl;
    return 0;
}

Codeforces 364 A Matrix 题解（矩形构造）

相关推荐