Codeforces Round #626 (Div.2) B.Count Subrectangles

题意： 给两个序列，元素只含 $1$1和 $0$0， $a$a序列长度为 $n$n， $b$b序列长度为 $m$m，将 $a$a看为列矩阵， $b$b 看为行矩阵， $c$c矩阵为 $a\ast b$a∗b得到的矩阵，现在问你可以从中截取多少个面积为 $area$area的矩阵。

题解： 预处理 $area$area的全部因子，注意处理的时候因子不能超过 $n$n和 $m$m中较大的。然后分别遍历序列 $a$a和序列 $b$b，每次计算连续都为 $1$1的子段中每个因子段各可以有多少个。假设矩阵两边长分别为 $c,d$c,d，则计算 $a$a中长度为 $c$c的子段 和 $b$b中长度为 $d$d的子段相乘，以及 $a$a中长度为 $d$d的子段 和 $b$b中长度为 $c$c的子段个数相乘之和即可。注意当 $a$a和 $b$b长度相等的情况只需加一次。

代码：（赛时写的比较丑陋，中间部分可以不用开 $longlong$long long的）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 4e4 + 10;
int a[N], b[N];
ll s1[N], s2[N];
int n, m;
ll area;
pair<ll, ll> p[N];

int main()
{
	scanf("%d%d%lld", &n, &m, &area);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
	
	int cnt = 0; ll Ma = max(n, m);
	for(ll i = 1; i * i <= area; i++) 
		if(area % i == 0 && area / i <= Ma) p[cnt++] = make_pair(i, area / i);

	for(int i = 1; i <= n; i++) {
		while(i <= n && a[i] == 0) i++;
		
		int j = i;
		while(j <= n && a[j] == 1) j++;
		for(int k = 0; k < cnt; k++) {
			ll x = p[k].first, y = p[k].second;
			if(j - i >= x) s1[x] += j - i - x + 1;
			if(x != y && j - i >= y) s1[y] += j - i - y + 1;
		} 
		i = j - 1;
	}
	
	for(int i = 1; i <= m; i++) {
		while(i <= m && b[i] == 0) i++;
		
		int j = i;
		while(j <= m && b[j] == 1) j++;
		for(int k = 0; k < cnt; k++) {
			ll x = p[k].first, y = p[k].second;
			if(j - i >= x) s2[x] += j - i - x + 1;
			if(x != y && j - i >= y) s2[y] += j - i - y + 1;
		}
		i = j - 1;
	}
	
	ll res = 0;
	for(int k = 0; k < cnt; k++) {
		ll x = p[k].first, y = p[k].second;
		res += s1[x] * s2[y];
		if(x != y) res += s2[x] * s1[y]; 
	}
	
	printf("%lld\n", res);
	
	return 0;
}