WUPC 2019 H - Doki Doki Programming Clubs!
問題
H - Doki Doki Programming Clubs!
問題概要
個の数列が与えられる。
番目の数列
の長さは
である。
クエリ
とは以下の通り:
- 数列
について、
を
で割った余りを答える
上記のクエリが個与えられるので、各クエリについて答えよ。
アイデア
まず、クエリについて、どのような処理になっているかを観察してみる。
以下では、クエリについて、
を仮定する。
数列
の方が長いので、短い方の数列
を長い方に揃えることになる。
例えば、
ならこんな感じ。
短い方の数列を長い方に周期的に揃えて、積の和について考える。
ここで、問題で与えられた通りに短い方を長い方に毎回揃えて計算してしまうとTLEするので、短い方に揃えて計算出来ないかを考える。
長い方のindexに注目してみると、短い方の長さの剰余によって、どの要素との積になっているかが決定している:
よって、クエリに対してで計算したい時、数列
を周期
で分類した和(上の例で言うと、数列
に関する赤の和と青の和と緑の和)を用意しておけば良いことになる。
以上の考察から、短い方の数列に揃えてクエリを処理するためには、前計算として各数列について、自分より短い周期について、その剰余で分類した和を用意しておく必要がある。
以下では、とする。
この前計算は
で実現することができる。
その理由については、実際に前計算のコードを見てみるとわかりやすい:
// 前計算 // k[i] のdistinctな要素を列挙 vector<int> uk(k); sort(uk.begin(), uk.end()); uk.erase(unique(uk.begin(), uk.end()), uk.end()); int UK = uk.size(); // 各数列 a[i] について、自分以下の周期の和を前計算 vector<vector<vector<long>>> sum(n, vector<vector<long>>(UK)); for(int i=0; i<n; ++i){ for(int j=0; j<UK; ++j){ int L = uk[j]; if(L > k[i]) break; sum[i][j] = vector<long>(L); for(int l=0; l<k[i]; ++l){ sum[i][j][l%L] += a[i][l]; sum[i][j][l%L] %= mod; } } }
のループと
のループを合わせて、ちょうど
回のループになっているので、ループが回る回数は
となっている。
ここで、
とは、
の種類数となっているが、数列の長さ
の種類数はたかだか
である。
できるだけ種類数が多くなるような状況を考えてみると、数列の長さはと、長さを1ずつ増やしながら1つずつ数列を用意する、という状況になる。
これを長さ
までもれなく揃えたとすると、長さの合計は
となり、
なので、種類数は
で抑えられていることが分かる。
以上で、前計算はであることが確認できた。
以下ではクエリ処理について確認する。
一度来たクエリについてはメモ化して答えることにし、新しいクエリについてはで計算することにすると、計算量は
となっている。
これを示すために、2つの場合に分けて考える:
のとき
1クエリに対してで処理できるので、クエリ全体について
で処理できる。
のとき
この場合は、となるような数列はたかだか
個しか存在しない。
この条件を満たす数列
に対して、
以外の数列とのクエリが全部与えられたとしても、そのクエリ合計で
で抑えられているのは明らか。
以上のことから、クエリ全体について
で処理できる。
以上より、計算量は全体でとなり、これは十分に高速である。
実装(C++)
#include <bits/stdc++.h> using namespace std; const long mod = 1e9+7; int main(){ int n; scanf(" %d", &n); vector<int> k(n); vector<vector<long>> a(n); for(int i=0; i<n; ++i){ scanf(" %d", &k[i]); a[i] = vector<long>(k[i]); for(int j=0; j<k[i]; ++j) scanf(" %ld", &a[i][j]); } // 前計算 // k[i] のdistinctな要素を列挙 vector<int> uk(k); sort(uk.begin(), uk.end()); uk.erase(unique(uk.begin(), uk.end()), uk.end()); int UK = uk.size(); // 各数列 a[i] について、自分以下の周期の和を前計算 vector<vector<vector<long>>> sum(n, vector<vector<long>>(UK)); for(int i=0; i<n; ++i){ for(int j=0; j<UK; ++j){ int L = uk[j]; if(L > k[i]) break; sum[i][j] = vector<long>(L); for(int l=0; l<k[i]; ++l){ sum[i][j][l%L] += a[i][l]; sum[i][j][l%L] %= mod; } } } // クエリ処理 int Q; scanf(" %d", &Q); map<pair<int,int>, long> memo; while(Q--){ int x,y; scanf(" %d %d", &x, &y); pair<int,int> p(min(x,y), max(x,y)); long ans = 0; if(memo.count(p)) ans = memo[p]; else{ if(k[x] > k[y]) swap(x,y); int uk_idx = lower_bound(uk.begin(), uk.end(), k[x]) - uk.begin(); for(int i=0; i<k[x]; ++i){ ans += a[x][i] * sum[y][uk_idx][i]; ans %= mod; } memo[p] = ans; } printf("%ld\n", ans); } return 0; }