原题地址：http://codeforces.com/problemset/problem/364/A
题目大意：
给定一个数字a（0 ≤ a ≤ 109）和一个数列s（每个数都是一位，长度不超过4000），定义一个矩阵Mij = si * sj ，求M有多少个子矩阵上面的数字和恰巧等于a
算法分析：
这道题是Codeforces Round #213 Div 1 Problem A && Div 2 Problem C，赛场上没写对，主要是没分析清楚，有一点想法就迫不及待地提交，结果白白提交了九次。后来以为自己想通了一个小BUG，转天又开始毛毛躁躁……看了数据才发现自己脑残忘了一种情况……教训十分沉重。
首先我们定义一个子矩阵为（x, y, z, t），意思为以矩阵中的点(x, y)为左上角，(z, t)为右下角的子矩形。我们需要通过观察发现对于某个子矩形上的元素和，恰巧等于
\( \sum\limits_{i=x}^{z} s_{i} * \sum\limits_{i=y}^{t} s_{i}\) (这一点很容易证明)。接下来我们要做的就是预处理出来一个部分和\( sum[i] = \sum\limits_{x=1}^{i} s_{x} \)，
然后我们就可以用\( n^2 \)的时间求出s上任意一段的部分和。设w[t]为t在所有的部分和中出现的次数（亦即：枚举i和j（i ≤ j），若i到j的部分和为t，++w[t]）
那么，我们要求的就是对于a的每个因子q,\( \sum\limits_{q | a} w[q] * w[a / q] \)。
至于接下来……就是几个需要注意的我脑残的地方了
- s的最大长度为4000，每一位的最大值是9，所以w最大只需要到36000，保险起见开到40000。
- 尽管任何一段的部分和都不会超过36000，但是w[a/q]很可能使数组越界，需要特判
- 如果a=0，需要进行特殊处理
//date 20131119
#include <cstdio>
#include <string>
#include <iostream>
#include <cstring> using namespace std; const int maxn = ;
const int maxa = ; long long a, ans;
string s;
int sum[maxn];
int w1[maxa]; int main()
{
//freopen("matrix.in", "r", stdin);
//freopen("matrix.out", "w", stdout);
cin >> a;
ans = ; //if(a == 0L){printf("0\n"); return 0;} cin >> s;
int l = s.length();
for(int i = ; i <= l; ++i) sum[i] = s[i - ] - '';
for(int i = ; i <= l; ++i)
sum[i] = sum[i - ] + sum[i]; for(int i = ; i <= l; ++i)
for(int j = ; j <= i; ++j)
w1[sum[i] - sum[j - ]]++; if(a > )
for(int i = ; i < maxa; ++i)
{
if(a % (long long)i == )
{
if((a / (long long)i) >= maxa)continue;
ans += (long long)w1[i] * (long long)w1[a / (long long)i];
}
} else{
for(int i = ; i < maxa; ++i)
ans += (long long)w1[] * (long long)w1[i];
ans *= 2L; ans += (long long)w1[] * (long long)w1[];
}
cout << ans << endl;
return ;
}
继续加油！