Codeforces Round #213 (Div. 1) A. Matrix

問題

codeforces.com

解法

長方形 (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;
}