Submission #4545413


Source Code Expand

Copy
#include <bits/stdc++.h>
#define N 1000000007
#define border 450
using namespace std;

long long n, q;
vector<vector<long long>> a;
vector<vector<vector<long long>>> memo;
map<pair<long long, long long>, long long> mp;

void setmemo();
long long solve(long long x, long long y);

int main() {
  cin >> n;
  a.resize(n);
  for(int i = 0; i < n; ++i) {
    long long k;
    cin >> k;
    a[i].resize(k);
    for(int j = 0; j < k; ++j) cin >> a[i][j];
  }
  setmemo();
  cin >> q;
  for(int i = 0; i < q; ++i) {
    long long x, y;
    cin >> x >> y;
    if(a[x].size() > a[y].size())
      swap(x, y);
    else if(a[x].size() == a[y].size() && x > y)
      swap(x, y);
    cout << solve(x, y) << endl;
  }
  return 0;
}

void setmemo() {
  memo.resize(n);
  for(int i = 0; i < n; ++i) {
    memo[i].resize(min((int)a[i].size(), border));
    int nowsize = memo[i].size();
    for(int j = 0; j < nowsize; ++j) {
      memo[i][j].resize(j + 1);
      for(int k = 0; k < a[i].size(); ++k) {
        memo[i][j][k % (j + 1)] += a[i][k];
        memo[i][j][k % (j + 1)] %= N;
      }
    }
  }
}

long long solve(long long x, long long y) {
  if(mp.find({x, y}) != mp.end()) return mp[{x, y}];
  long long ans = 0, nowsize = a[x].size();
  if(nowsize >= border) {
    nowsize = a[y].size();
    for(long long i = 0; i < nowsize; ++i) {
      ans += a[x][i % a[x].size()] * a[y][i] % N;
      ans %= N;
    }
    return mp[{x, y}] = ans;
  }
  for(int i = 0; i < nowsize; ++i) {
    ans += a[x][i] * memo[y][nowsize - 1][i] % N;
    ans %= N;
  }
  return mp[{x, y}] = ans;
}

Submission Info

Submission Time
Task H - Doki Doki Programming Clubs!
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1635 Byte
Status
Exec Time 1367 ms
Memory 281088 KB

Test Cases

Set Name Score / Max Score Test Cases
All 200 / 200 0-sample-1, 0-sample-2, 0-sample1, 0-sample2, 1-random-large-0, 1-random-large-1, 1-random-large-2, 1-random-large-3, 1-random-large-4, 1-random-large-5, 1-random-large-6, 1-random-large-7, 1-random-large-8, 1-random-large-9, 2-challenge-0, 2-challenge-1, 2-challenge-2, 2-challenge-3, 2-challenge-4, 2-challenge-5, 2-challenge-6, 2-challenge-7, 2-challenge-8, 2-challenge-9, 3-challenge2-0, 3-challenge2-1, 3-challenge2-2, 3-challenge2-3, 3-challenge2-4, 3-challenge2-5, 3-challenge2-6, 3-challenge2-7, 3-challenge2-8, 3-challenge2-9, 4-maximum-0, 4-maximum-1, 5-increase-0, 5-increase-1, 6-increase2-0, 6-increase2-1, 7-nomemo-0, 7-nomemo-1
Case Name Status Exec Time Memory
0-sample-1 1 ms 256 KB
0-sample-2 1 ms 256 KB
0-sample1 1 ms 256 KB
0-sample2 1 ms 256 KB
1-random-large-0 986 ms 32128 KB
1-random-large-1 1037 ms 25856 KB
1-random-large-2 846 ms 45184 KB
1-random-large-3 1016 ms 28032 KB
1-random-large-4 1037 ms 24960 KB
1-random-large-5 913 ms 40576 KB
1-random-large-6 1024 ms 28800 KB
1-random-large-7 1001 ms 28672 KB
1-random-large-8 1031 ms 28672 KB
1-random-large-9 948 ms 35584 KB
2-challenge-0 815 ms 25856 KB
2-challenge-1 761 ms 14208 KB
2-challenge-2 737 ms 13184 KB
2-challenge-3 742 ms 13952 KB
2-challenge-4 749 ms 15232 KB
2-challenge-5 729 ms 16640 KB
2-challenge-6 750 ms 19200 KB
2-challenge-7 741 ms 20992 KB
2-challenge-8 744 ms 21760 KB
2-challenge-9 744 ms 22528 KB
3-challenge2-0 809 ms 24064 KB
3-challenge2-1 792 ms 14336 KB
3-challenge2-2 763 ms 13440 KB
3-challenge2-3 762 ms 14336 KB
3-challenge2-4 737 ms 15616 KB
3-challenge2-5 742 ms 17024 KB
3-challenge2-6 737 ms 19584 KB
3-challenge2-7 741 ms 21376 KB
3-challenge2-8 748 ms 22144 KB
3-challenge2-9 748 ms 22912 KB
4-maximum-0 817 ms 42752 KB
4-maximum-1 797 ms 42752 KB
5-increase-0 1361 ms 281088 KB
5-increase-1 1367 ms 281088 KB
6-increase2-0 1106 ms 129792 KB
6-increase2-1 1118 ms 129792 KB
7-nomemo-0 871 ms 5376 KB
7-nomemo-1 872 ms 5376 KB