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;
}