AcWing 3617. 子矩形计数
原题链接
中等
作者:
Youbuhua
,
2021-06-03 18:30:16
,
所有人可见
,
阅读 176
#include<bits/stdc++.h>
#define ll long long
using namespace std;
set<int> st;
const int N = 1e5;
int m1[N],m2[N];
int cha1[N],cha2[N];
int main()
{
int n,m,k,t,pre = 0,cnt = 0,flag;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> t;
if(t){
cnt++;
cha1[1]++;
cha1[cnt+1]--;
}
else if(i != n-1){
cnt = 0;
}
}
cnt = 0;
for(int i = 0; i < m; i++){
cin >> t;
if(t){
cnt++;
cha2[1]++;
cha2[cnt+1]--;
}
else if(i != m-1){
cnt = 0;
}
}
for(int i = 1; i*i <= k; i++){
if(k % i == 0){
st.insert(i);
st.insert(k / i);
}
}
set<int> ::iterator it;
int a,b;
ll ans = 0;
for(int i = 1; i <= N; i++){
m1[i] = cha1[i] + m1[i-1];
m2[i] = cha2[i] + m2[i-1];
}
for(it = st.begin(); it != st.end(); it++){
a = *it;
b = k / a;
if(a > n || b > m){
continue;
}
ans += m1[a] * m2[b];
}
cout << ans << endl;
return 0;
}