けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 159 E - Dividing Chocolate (水色, 500 点)

制約が縦方向の bit 管理を要求している感満載

問題へのリンク

問題概要

 H \times W のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が  K 以下になるようにする。

これを実現できるような、ラインの本数の最小値を求めよ。

制約

  •  1 \le H \le 10
  •  1 \le W \le 1000

考えたこと

縦横両方を考えるのは大変なので、どちらかを固定したくなる...と思っていたところに、 H \le 10 という制約が飛び込んできた。これはもう

  • 横のラインの引き方 ( 2^{H-1} 通りある) を決め打ちして全探索せよ

ということだ。ここまで思うともう簡単で、縦のラインは、Greedy でよい。つまり、

  • 最後に縦のラインを引いた地点から
  •  K を超えないギリギリのところまで引っ張って
  • 限界を超える手前でラインを引く

という風な Greedy で OK。ギリギリまで引っ張ることをせずに縦のラインを引く意味はないからだ。計算量は [tex: O(2H HW)]。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int H, W, K;
vector<string> fi;

int solve() {
    int res = 1<<29;
    for (int bit = 0; bit < (1<<(H-1)); ++bit) {
        bool gok = true; // そもそも不可能な場合もあるので判定
        int N = 0;
        vector<int> ord(H, 0);
        for (int i = 0; i < H-1; ++i) {
            if (!(bit & (1<<i))) ord[i+1] = ord[i];
            else ord[i+1] = ord[i]+1, ++N;
        }
        int add = 0;
        vector<int> nums(N+1, 0);
        for (int w = 0; w < W; ++w) {
            vector<int> one(N+1, 0);
            bool ok = true;
            for (int h = 0; h < H; ++h) {
                one[ord[h]] += fi[h][w] - '0';
                nums[ord[h]] += fi[h][w] - '0';
                if (one[ord[h]] > K) gok = false;
                if (nums[ord[h]] > K) ok = false;
            }
            if (!ok) ++add, nums = one;
        }
        if (gok) chmin(res, N + add);
    }
    return res;
}

int main() {
    cin >> H >> W >> K;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    cout << solve() << endl;
}

AtCoder ABC 159 F - Knapsack for All Segments (青色, 600 点)

ごちゃごちゃとばぐらせながら何とか通した...

問題へのリンク

問題概要

 N 要素の数列  A_{1}, \dots, A_{N} が与えられる。この数列の  N(N+1)/2 通りの区間それぞれについての

  • 区間内の要素の部分集合であって総和が  S であるものの個数

の総和を求め、998244353 で割ったあまりを求めよ。

制約

  •  1 \le N, S \le A_{i} \le 3000

考えたこと

まず、区間が数列全体の場合についての答えなら、普通の部分和問題を解くような DP で解くことができる。その場合の計算量は  O(NS) となる。しかし計算量的にはもうこれ以上増やせないことがわかる。愚直にやったのでは  O(N^{3}S) となる。なんとかしなければならない。

まずは、この手の問題でよくあることとして、見方を変えるというのがある。問題は「各区間についての総和」だが、逆に

  • 和が S となるような要素の選び方それぞれについて
  • その要素たちを包含するような区間が何個あるかを合計する

という風に考えてみる。少し可能性ありそうな見た目になった。この個数は具体的には、

  • 和が S となる要素の選び方を一つとってきたとき、
  • それらを包含する極小な区間が [left, right) であるとき、
  • 包含する区間の個数は (left + 1) × (N - right + 1) 通りある

ということがわかるので、これを合計すればよい。左端を固定して考えたくなるのだが、それでは計算量が間に合わないので、何とか工夫することを考える。やり方はいくつかありそう。

解法(1): いわゆる耳 DP

状態遷移を意識する DP。今回は

  • まだ左端を選択していない状態 (状態 0)
  • 左端は選択済みだけど右端は選択していない状態 (状態 1)
  • 右端も選択済みの状態 (状態 2)

という状態遷移を素直に落とし込めば OK。通称、耳 DP。

  • dp[ i ][ j ][ t ] := 最初の i 個の要素について、総和が j で、状態が t である場合の場合の数

とする。左端の重みは i + 1、右端の重みは N - i とする感じで遷移すれば OK。

#include <bits/stdc++.h>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

int N, S;
vector<int> A;

mint solve() {
    vector<vector<vector<mint>>> dp(N+1, vector<vector<mint>>(6500, vector<mint>(3, 0)));
    dp[0][0][0] = 1;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= S; ++j) {
            // from 0
            dp[i+1][j][0] += dp[i][j][0];
            dp[i+1][j+A[i]][1] += dp[i][j][0] * (i+1);
            dp[i+1][j+A[i]][2] += dp[i][j][0] * (i+1) * (N-i);

            // from 1
            dp[i+1][j][1] += dp[i][j][1];
            dp[i+1][j+A[i]][1] += dp[i][j][1];
            dp[i+1][j+A[i]][2] += dp[i][j][1] * (N-i);

            // from 2
            dp[i+1][j][2] += dp[i][j][2];
        }
    }
    return dp[N][S][2];
}

int main() {
    cin >> N >> S;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}

解法(2): 本番でやった

僕は DP の定義自体に、左端の選択肢に関する場合の数も含めてしまうことにした。

  • dp[ i ][ j ] := 最初の i 個の要素の中から総和を j にする選び方と、その選んだ要素をすべて包含するような区間の左端の取り方との組の個数

として定義した。dp の更新は

  • dp[ i + 1 ][ A[ i ] ] += i + 1 (左端の選び方も含む)
  • j > 0 について、dp[ i + 1 ][ j + A[ i ] ] += dp[ i ][ j ] (左端は固定済み)

という風にできる。そして、dp の第二添字が S になる瞬間について、すなわち dp[ i ][ j ] が dp[ i + 1 ][ S ] へと更新されるタイミングで

  • dp[ i ][ j ] × (N - i)

の値を答えに合算していく。計算量は  O(NS)

#include <bits/stdc++.h>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

int N, S;
vector<int> A;

mint solve() {
    mint res = 0;
    vector<vector<mint>> dp(N+1, vector<mint>(S+1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= S; ++j) dp[i+1][j] += dp[i][j];
        if (A[i] <= S) dp[i+1][A[i]] += i+1;
        for (int j = 1; j <= S; ++j) if (A[i] + j <= S) dp[i+1][j+A[i]] += dp[i][j];

        if (A[i] == S) res += (i+1) * (N-i);
        for (int j = 1; j <= S; ++j) if (A[i] + j == S) res += dp[i][j] * (N - i);
    }
    return res;
}

int main() {
    cin >> N >> S;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}

AtCoder AGC 018 A - Getting Difference (緑色, 300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。

問題へのリンク

問題概要

要素数  N の数列  A_{0}, \dots, A_{N-1} が与えられる。これに対して以下の操作を好きな回数だけ行うことができる:

  • 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する

整数  K を出現させられるかどうかを判定せよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

「最大公約数」ん関する話題をこの記事に集大成した。

qiita.com

この中で、以下のような Euclid の互除法の原理を紹介した。

  • GCD(a, b) = GCD(a-b, b)

今回の操作はまさにこれっぽさがある。そして Euclid の互除法をシミュレートすることで、数列  A_{1}, A_{2}, \dots, A_{N-1} の最大公約数  g を作ることができる。

さらに  g の倍数のうち、 A の最大値以下のものはすべて作ることができる。 A の最大値より大きいものは作れない。

#include <bits/stdc++.h>
using namespace std;

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    return GCD(y, x%y);
}

int main() {
    int N;
    long long K;
    cin >> N >> K;
    long long ma = 0, g = 0;
    for (int i = 0; i < N; ++i) {
        long long a; cin >> a;
        ma = max(ma, a);
        g = GCD(g, a);
    }
    if (K <= ma && K % g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}

AtCoder AGC 043 D - Merge Triplets (橙色, 1200 点)

めちゃくちゃ楽しかった

問題へのリンク

問題概要

長さ  3 の数列を  N 個用意する。ただしこれらのなす  3N 個の値は  1, 2, \dots, 3N が 1 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ  3N の順列を作る。

  • 空にならずに残っている数列のうち、先頭の要素のみをみたときの最小値を pop して、
  • それを現在形成されている順列の最後尾に加える

作られうる順列の個数を素数  M で割ったあまりを求めよ。

制約

  •  1 \le N \le 2000

考えたこと

入力が実質的に  N の 1 個だけという好きなタイプの問題。埋め込みを封じるために mod も入力として指定されているわけだ。

さて、こういう「操作の結果出来上がるものが何通りありますか」という問題では、操作過程をまともに追いかけてはいけないと痛感している。まずはじめに「こういう順列を作れますか?」という判定問題を解くのだ。それがわかりやすい形で解けると数え上げもできる、というパターンはあまりにも多い。

というわけで、作れる順列の条件を考えよう。色々やっているとまず

  • 3, 8, 5, 4, 2, 6, 1, 7, 9

とかを例にとったとき、(8, 5, 4, 2) という並びで既に詰んでいることがわかる。なぜなら、8 を拾う時点で (5, 4, 2) はむき出しになってはいけないので他レーンに置くことができないのだ。これらは 8 の後ろに並んでなければならない。したがって

  • 要素 x に対して、そこから先に最初に x より大きい要素が出てくるまでの間に、x を含めて 4 個以上の要素がある状態は実現できない

ということがわかった。ここから、

  • 要素 x に対して、最初に x より大きいものが出てくるまでをひとまとめにしたブロック

に分けて考えることにした。このとき、大きさ 2 のブロックを同じレーンに複数個入れることもできないこともわかる。よって必要条件を書き出すと


  • ブロックの大きさは 3 以下でなければならない
  • 大きさが 2 以上のブロックは  N 個以下でなければならない

というのが抽出された。そして色々手を動かしてみると、これが十分条件っぽい。実際

  • 大きさ 3 のブロックは新規レーンに突っ込んでおけばよい
  • 大きさ 2 のブロックは、どこか隙間か、新規レーンに突っ込んでおけば良い
  • 大きさ 1 のブロックは好きにしてよい

という方法で問題ないことがわかる。基本的にブロックの先頭要素は単調増加なので、ブロック単位でまとめて順列に挿入されていくことは保証されるし、その順序がブロック順になることも保証される。

他視点:最大の要素に着目

解説でも、他の多くの方のコメントを見ても、「まず最大の要素に着目して...」という視点から、同じ条件に行き着いた方は多かったみたいだ。僕はあまりそこを意識できていなかった。アルメリアさんの記事にこの着眼点からの導出がある。

DP へ

以上の条件を抽出できたらもう簡単だ。

  • dp[ i ][ j ] := 1, 2, ..., i の順列であって、大きさ 2 以上のブロックが j 個あるような場合の数

とすると、遷移は新規ブロックサイズが 1, 2, 3 の場合に場合分けして挿入 DP すれば OK。

  • dp[ i + 1 ][ j ] += dp[ i ][ j ] (新規挿入が最大値でなければならない)
  • dp[ i + 2 ][ j + 1 ] += dp[ i ][ j ] × (i + 1) (新規挿入の先頭は最大値だが、2 個目の値は i + 1 通り考えられる)
  • dp[ i + 3 ][ j + 1 ] += dp[ i ][ j ] × (i + 2)(i + 1)

という感じ。計算量は O(N2) となる。

#include <bits/stdc++.h>
using namespace std;

// dynamic modint
vector<int> MODS = { 1000000007 }; // 実行時に決まる
template<int IND = 0> struct Fp {
    long long val;
    
    int MOD = MODS[IND];
    constexpr Fp(long long v = 0) noexcept : val(v % MODS[IND]) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<IND>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<IND>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<IND> modpow(const Fp<IND> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<>;
mint solve(int N) {
    vector<vector<mint>> dp(N*3+1, vector<mint>(N+1, 0));
    dp[0][0] = 1;
    for (long long i = 0; i <= N*3; ++i) {
        for (long long j = 0; j <= N; ++j) {
            if (i+1 <= N*3) {
                dp[i+1][j] += dp[i][j];
            }
            if (i+2 <= N*3 && j+1 <= N) {
                dp[i+2][j+1] += dp[i][j] * (i+1);
            }
            if (i+3 <= N*3 && j+1 <= N) {
                dp[i+3][j+1] += dp[i][j] * (i+2) * (i+1);
            }
        }
    }
    mint res = 0;
    for (int j = 0; j <= N; ++j) res += dp[N*3][j];
    return res;
}

int main() {
    int N;
    cin >> N >> MODS[0];
    cout << solve(N) << endl;
}

AtCoder AGC 043 C - Giant Graph (赤色, 900 点)

これはマジで天才やと思うやが...
いや本当にどこから Grundy 数を導けるのか、わからぬ...

問題へのリンク

問題概要

頂点数  N のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数  N^{3} のカルテシアングラフの独立集合のうち、以下の値の最大値を求め、それを 998244353 で割ったあまりを求めよ。

  • 独立集合に含まれる各頂点 (a, b, c) (それぞれのグラフの頂点番号に相当, 1-indexed) について、重みとして  10^{18(a + b + c)} を加算する

制約

  •  2 \le N \le 10^{5}
  • 各グラフの辺数は  10^{5} 以下

考えたこと

まずグラフが 1 個の場合を考えてみると、単純に、頂点番号が大きい順に Greedy にとっていけばよいことがわかる。その際に

  • 今見ている頂点から行ける頂点 (番号が大きい方向へ) のうち、
    • 1 つでも採用済みの頂点があったら採用できない
    • すべて採用していない頂点であれば採用する

という風にすれば OK。そしてこの営みが、なんと Game DP にそっくりだというのだ。言われてみれば確かに...

  • 「採用済み」を「負け」
  • 「採用しない」を「勝ち」

と言い換えると、ピッタリ対応する手続きになっている。そしてカルテシアングラフ上のこの手続きは、「3 つの山に関する Nim」に対応するという。

Grundy 数

というわけで、それぞれのグラフのそれぞれの頂点について、「採用する」を 0 として、Grundy 数を求めてあげる。

そうすると、頂点 (a, b, c) が採用されるかどうかは、Grundy 数の XOR 和が 0 かどうかで判定できるのだ。

...どうしたらこんな発想が生まれるのかわからないけど、とりあえず「頂点 (a, b, c) が採用されるための必要十分条件をじっくり考察する」というのをやるといいのかもしれない。そうするともしかしたら自然に Grundy 数と似ていることに思い至るか、Grundy 数と同等の概念を自力で再発明できるのかもしれない。

Grundy 数は小さい

そしてさらに、Grundy 数は辺数を  M として、 O(\sqrt{M}) 程度の大きさにしかならないという。それはそうだと思う。よってこの問題は、

  • 3 つのグラフそれぞれについて、各頂点の Grundy 数を求め
  • それを Grundy 数の値ごとに集計した配列を作る (そのサイズは  O(\sqrt{M}) 程度で十分)
  • 3 つのうちの 2 つについて全探索して、計算量は  O(M)

というわけだ。

#include <bits/stdc++.h>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

using Graph = vector<vector<int>>;
int N;
vector<int> M;
vector<Graph> G;
vector<mint> ten;

void pre() {
    int MAX = 510000;
    ten.assign(MAX, 1);
    mint fac = modpow(mint(10), 18);
    for (int i = 1; i <= MAX; ++i) ten[i] = ten[i-1] * fac;
}

mint solve() {
    vector<vector<int>> grundy(3, vector<int>(N, -1));
    vector<vector<mint>> memo(3, vector<mint>(1000, 0));
    for (int iter = 0; iter < 3; ++iter) {
        for (int v = N-1; v >= 0; --v) {
            set<int> gse;
            for (auto e : G[iter][v]) gse.insert(grundy[iter][e]);
            int gres = 0;
            while (gse.count(gres)) ++gres;
            grundy[iter][v] = gres;
            memo[iter][gres] += ten[v+1];
        }
    }
    mint res = 0;
    for (int a = 0; a < 1000; ++a) {
        if (memo[0][a] == 0) break;
        for (int b = 0; b < 1000; ++b) {
            if (memo[1][b] == 0) break;
            int c = a^b;
            res += memo[0][a] * memo[1][b] * memo[2][c];
        }
    }
    return res;
}

int main() {
    pre();
    cin >> N;
    M.assign(3, 0);
    G.assign(3, Graph(N, vector<int>()));
    for (int iter = 0; iter < 3; ++iter) {
        cin >> M[iter];
        for (int i = 0; i < M[iter]; ++i) {
            int a, b; cin >> a >> b; --a, --b;
            G[iter][a].push_back(b);
            G[iter][b].push_back(a);
        }
    }
    cout << solve() << endl;
}