間に合わず。

problem

$N + N$個の頂点からなる$2$部グラフを考える。 $2$つの集合を左側右側とし、それぞれの側の頂点に$0, 1, \dots, N-1$番と番号を付けておく。 初期状態では$i$番の対応する左右の頂点の間に辺がそれぞれ$1$本張られている。 以下のクエリを処理せよ。

  • $i, j, s$が与えられる。$|i - j| \le 1$である。左の$i$番目の頂点と右の$j$番目の頂点の間に辺を$s$本張って更新し、その後の最大$2$部マッチングの個数を答えよ。

solution

segment木。長さ$1$の区間には注意。$O(M \log N)$。

頂点を並べて区間ごとに計算し合成していく。 $i$番目と辺があるのは$i-1, i, i+1$番目だけなので、$i$番目から$i+1$番目への辺を使えば必ず$i+1$番目から$i$番目への辺も使われる。これにより、区間の両端での辺の使い方だけ持てば計算できる。

implementation

#include <iostream>
#include <vector>
#include <functional>
#include <cmath>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;

template <typename T>
struct segment_tree { // on monoid
    int n;
    vector<T> a;
    function<T (T,T)> append; // associative
    T unit; // unit
    segment_tree() = default;
    segment_tree(int a_n, T a_unit, function<T (T,T)> a_append) {
        n = pow(2,ceil(log2(a_n)));
        a.resize(2*n-1, a_unit);
        unit = a_unit;
        append = a_append;
    }
    void point_update(int i, T z) {
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = append(a[2*i-1], a[2*i]);
        }
    }
    T range_concat(int l, int r) {
        return range_concat(0, 0, n, l, r);
    }
    T range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) {
            return a[i];
        } else if (ir <= l or r <= il) {
            return unit;
        } else {
            return append(
                    range_concat(2*i+1, il, (il+ir)/2, l, r),
                    range_concat(2*i+2, (il+ir)/2, ir, l, r));
        }
    }
};

const int mod = 1e9+7;
struct spell_t {
    int down, eql, up;
};
struct range_t {
    int length;
    spell_t l, r;
    int dp[2][2]; // { EQL, UP } x { EQL, DOWN }
};
range_t unit() {
    range_t a = {};
    return a;
}
range_t append(range_t const & a, range_t const & b) {
    if (a.length == 0) return b;
    if (b.length == 0) return a;
    range_t c = {};
    c.length = a.length + b.length;
    c.l = a.l;
    c.r = b.r;
    if (a.length == 1 and b.length == 1) {
        c.dp[0][0] = 1;
        c.dp[1][1] = 1;
        c.r = b.l;
    } else if (a.length == 1) {
        assert (false);
    } else if (b.length == 1) {
        repeat (x,2) {
            ll acc = 0;
            acc += a.dp[x][0] *(ll) a.r.eql  % mod;
            acc += a.dp[x][1] *(ll) a.r.down % mod;
            c.dp[x][0] = acc % mod;
        }
        repeat (x,2) {
            c.dp[x][1] = a.dp[x][0] *(ll) a.r.up % mod;
        }
        c.r = b.l;
    } else {
        repeat (x,2) repeat (y,2) {
            ll acc = 0;
            acc += a.dp[x][0] *(ll) a.r.eql  % mod * b.l.eql  % mod * b.dp[0][y] % mod;
            acc += a.dp[x][0] *(ll) a.r.eql  % mod * b.l.up   % mod * b.dp[1][y] % mod;
            acc += a.dp[x][1] *(ll) a.r.down % mod * b.l.eql  % mod * b.dp[0][y] % mod;
            acc += a.dp[x][1] *(ll) a.r.down % mod * b.l.up   % mod * b.dp[1][y] % mod;
            acc += a.dp[x][0] *(ll) a.r.up   % mod * b.l.down % mod * b.dp[0][y] % mod;
            c.dp[x][y] = acc % mod;
        }
    }
    return c;
}

int solve(int n, int m, vector<int> const & w, vector<int> const & z, vector<int> const & s) {
    int result = 0;
    if (n == 1) {
        int acc = 1;
        repeat (i,m) {
            acc = (acc + s[i]) % mod;
            result = (result + acc) % mod;
        }
    } else {
        segment_tree<range_t> segtree(n, unit(), append);
        vector<spell_t> spell(n); // spell : wand x { DOWN, EQL, UP } -> number
        auto update = [&](int i) {
            range_t a = {};
            a.length = 1;
            a.l = spell[i];
            a.r = { 0, 1, 0 };
            a.dp[0][0] = 1;
            segtree.point_update(i, a);
        };
        repeat (i,n) {
            spell[i] = { 0, 1, 0 };
            update(i);
        }
        repeat (i,m) {
            int j = w[i] - 1;
            int d = z[i] - w[i] + 1;
            int *it;
            switch (d) {
                case 0: it = &spell[j].down; break;
                case 1: it = &spell[j].eql;  break;
                case 2: it = &spell[j].up;   break;
            }
            *it = (*it + s[i]) % mod;
            update(j);
            range_t a = segtree.range_concat(0, n);
            ll acc = 0;
            acc += a.l.eql *(ll) a.dp[0][0] % mod * a.r.eql  % mod;
            acc += a.l.eql *(ll) a.dp[0][1] % mod * a.r.down % mod;
            acc += a.l.up  *(ll) a.dp[1][0] % mod * a.r.eql  % mod;
            acc += a.l.up  *(ll) a.dp[1][1] % mod * a.r.down % mod;
            result = (result + acc) % mod;
        }
    }
    return result;
}
int main() {
    int t; cin >> t;
    repeat (i,t) {
        int n, m; cin >> n >> m;
        vector<int> w(m), d(m), s(m);
        int aw, bw; cin >> w[0] >> aw >> bw;
        int ad, bd; cin >> d[0] >> ad >> bd;
        int as, bs; cin >> s[0] >> as >> bs;
        repeat (i,m-1) {
            w[i+1] = (w[i] *(ll) aw + bw) % n + 1;
            d[i+1] = (d[i] *(ll) ad + bd) % 3;
            s[i+1] = (s[i] *(ll) as + bs) % int(1e9) + 1;
        }
        vector<int> z(m);
        repeat (i,m) z[i] = max(1, min(n, w[i] + d[i] - 1));
        cout << "Case #" << i+1 << ": " << solve(n, m, w, z, s) << endl;
    }
    return 0;
}