Codeforces Round #213 (Div. 1) A. Matrix
解法
長方形 (x, y, z, t) における要素の和は, (s の x, y における和) * (s の z, t における和) となります。
なので, あらかじめ s の和が合計 b になるような場合の数を列挙して, a != 0 の時は, a = b*c となる b, c の候補を列挙して場合の数を掛け算すれば大丈夫です。
a = 0 の時は, s のどちらかの和が 0 になっていれば何でも良いので, 両方共 和が 0 になっていないような選び方 を全体から引けば良いです。
int sum[4444]; ll baai[40000]; int main() { cin.tie(0); ios::sync_with_stdio(false); int a; cin >> a; string s; cin >> s; int n = s.size(); for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + (s[i-1]-'0'); for (int l = 1; l <= n; l++) for (int r = l; r <= n; r++) { baai[sum[r]-sum[l-1]]++; } ll ans = 0; if (a == 0) { ll c1 = 0; for (int i = 1; i < 40000; i++) c1 += baai[i]; ll total = c1+baai[0]; ans = total*total - c1*c1; cout << ans << endl; return 0; } for (int d = 1; d * d <= a; d++) { if (a%d != 0) continue; if (a/d < 40000) { ll tmp = baai[d]*baai[a/d]; if (d*d != a) tmp *= 2; ans += tmp; } } cout << ans << endl; return 0; }