SRM 671 Div2 Medium BearDartsDiv2

本番普通にとけなかった。DP じゃ時間に間に合わないってのはわかってたんだけど。
SRM 668 Div2 Hard AnArray - shifth’s blog とかとほとんど同じようなパターンの問題だった。まだ復習してなかったので...。
w[a]*w[b] で int overflow するのを最初見落としてしまった。
これでこの手の問題は解けるようになったはず。(願望)

class BearDartsDiv2 {
public:
long long count(vector <int> w) {
        int n = w.size();
        const int maxW = (int)1E+6;

        // ある b の時点で右側にある w[d]/w[c] となるような (c,d) の組み合わせ数
        vector<int> num(maxW+1,0);

        ll cnt = 0;
        // (a,b) を全探索するとき高速で
        //
        //  w[a]*w[b] == w[d]/w[c]
        //
        // なるような w[d]/w[c] が計算できればよい。
        // b を降順に走査していけば、このような c,d はすでに前の b で現れていることになる。
        // よって各 b 毎に更新していけばよい。
        //
        for (int b = n-1; b >= 0; --b)
        {
            REP(a,b)
            {
                if ((ll)w[a]*w[b] <= maxW)
                    cnt += num[w[a]*w[b]];
            }
            FOR(d,b+1,n)
            {
                if (w[d] % w[b] == 0)
                    ++num[w[d]/w[b]];
            }
        }
        return cnt;
}
};