Submission #5307232

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
using namespace std;
template <int32_t MOD>
struct mint {
    int32_t value;
    mint() = default;
    mint(int32_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
};
constexpr int MOD = 1e9 + 7;
constexpr int SQRT = 500;
class solver {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
using namespace std;

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() = default;
    mint(int32_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
};


constexpr int MOD = 1e9 + 7;

constexpr int SQRT = 500;
class solver {
    int n;
    vector<vector<mint<MOD> > > a;
    vector<vector<vector<mint<MOD> > > > b;
    map<pair<int, int>, mint<MOD> > memo;

public:
    solver(int n_, const vector<vector<mint<MOD> > > & a_)
            : n(n_), a(a_) {
        b.resize(n);
        REP (i, n) {
            int k = min<int>(SQRT, a[i].size());
            b[i].resize(k);
            REP3 (k1, 1, k) {
                b[i][k1].resize(k1);
                REP (j, k1) {
                    for (int j1 = j; j1 < a[i].size(); j1 += k1) {
                        b[i][k1][j] += a[i][j1];
                    }
                }
            }
        }
    }

    mint<MOD> operator () (int x, int y) {
        auto key = minmax({ x, y });
        if (memo.count(key)) return memo[key];

        if (a[x].size() < a[y].size()) {
            swap(x, y);
        }
        int kx = a[x].size();
        int ky = a[y].size();
        assert (kx >= ky);

        mint<MOD> acc = 0;
        if (kx >= SQRT and ky < SQRT) {
            REP (j, ky) {
                acc += b[x][ky][j] * a[y][j];
            }
        } else {
            REP (j, kx) {
                acc += a[x][j] * a[y][j % ky];
            }
        }

        return memo[key] = acc;
    }
};

int main() {
    int n; cin >> n;
    vector<vector<mint<MOD> > > a(n);
    REP (i, n) {
        int k; cin >> k;
        a[i].resize(k);
        REP (j, k) {
            int a_i_j; cin >> a_i_j;
            a[i][j] = a_i_j;
        }
    }

    solver f(n, a);

    int q; cin >> q;
    while (q --) {
        int x, y; cin >> x >> y;
        cout << f(x, y).value << endl;
    }
    return 0;
}

Submission Info

Judge Result