给定一个由数字（0-9）构成的字符串s。我们可以由此定义出size(s) * size(s) 大
小的矩阵b，其中b[i][j] = s[i] * s[j]；请问在这个矩阵b中，有多少子矩形满足其中的b[i][j]的和为另一个给定的数字a。

Input

第一行一个整数a。
第二行字符串s。

Output

一个整数表示满足条件的子矩形数。

Sample Input

10
12345

Sample Output

6
【样例解释】
b 矩阵为：
01 02 03 04 05
02 04 06 08 10
03 06 09 12 15
04 08 12 16 20
05 10 15 20 25
和为 10 的子矩形有：
一、01 02 03 04
二、
01
02
03
04
三、04 06
四、
04
06
五、10
六、10
以上共六个。

Data Constraint

对10%的输入数据：size(s)≤10
对30%的输入数据：size(s)≤100
对100%的输入数据：0 ≤a≤1000000000，size(s)≤4000

Solution

对于10%的数据

O(n^6) 暴力

对于30%的数据

用前缀和优化 O(n^4)

对于100%的数据

注意到s最大也就才4000，数字为0~9，前缀和最大为4000*9=36000

令c[x]表示s一段和为x的个数

因为 a = x * (a / x)

则 x 和 (a / x) 都为 a 的约数且为整数

把 c[x] 和 c[a / x] 乘起来累加

注意特判 a = 0 的情况

比赛时漏了。。

code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<queue>
 7 #include<vector>
 8 #include<stack>
 9 #include<set>
10 #include<deque>
11 #include<map>
12 using namespace std;
13 
14 template <typename T> void read(T &x) {
15     x = 0; int f = 1; char c;
16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
18     x *= f;
19 }
20 template <typename T> void write(T x){
21     if (x < 0) putchar('-'), x = -x;
22     if (x > 9) write(x / 10);
23     putchar(x % 10 + '0');
24 }
25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
27 
28 #define int long long
29 #define inf 1234567890
30 #define next net
31 #define P 1000000007
32 #define N 4005
33 #define mid ((l+r)>>1)
34 #define lson (o<<1)
35 #define rson (o<<1|1)
36 #define R register
37 
38 int n,goal,ans;
39 int a[N],b[N],c[40010];
40 char s[N];
41 signed main(){
42     read(goal);
43     scanf("%s",s+1);
44     n=strlen(s+1);
45     for(R int i=1;i<=n;i++)a[i]=s[i]-'0',b[i]=b[i-1]+a[i];
46     for(R int i=1;i<=n;i++)
47         for(R int j=0;j<i;j++)
48             c[b[i]-b[j]]++;
49     if(goal==0){
50         for(R int i=0;i<=40000;i++)ans+=c[0]*c[i];
51         ans<<=1;ans-=c[0]*c[0];
52         writeln(ans);
53         return 0;
54     }
55     for(R int i=1;i<=40000;i++){
56         if(goal%i==0&&i*40000>=goal){
57             ans+=c[i]*c[goal/i];
58         }
59     }
60     writeln(ans);
61     return 0;
62 }

20200721T1 【NOIP2015模拟10.22】矩形 Description Input Output Sample Input Sample Output Data Constraint Solution code