Official

F - We're teapots Editorial by sheyasutaka

下位問題の考察

\(a_1 = \dots = a_{N-1} = -1\), \(a_N = r \neq -1\) である場合を考える．つまり，

(問題 NOADJ) 一列に並んだ \(N\) 個のティーポットのうち \(r\) 個を選ぶ方法であって，どの隣り合う \(2\) つも同時に選ばないものは何通りか？

という問題を考える．これの答えは，以下の問題の答えに等しい．

(問題 SIMPLE) \(N - (r-1)\) 個のティーポットから自由に \(r\) 個を選ぶ方法は何通りか？

このことをいうには，問題 NOADJ での選び方と問題 SIMPLE での選び方のあいだに一対一対応があることを示せばよい．

SIMPLE で選んだティーポットの番号を昇順に \(i_1, \dots, i_r\) とする．このとき，ティーポット \(i_2, \dots, i_r\) の左に \(1\) つずつティーポットを挿入することで，NOADJ での任意の選び方が再現できる．

逆に，NOADJ で選んだティーポットの番号を昇順に \(i_1, \dots, i_r\) とする．このとき，ティーポット \(i_2, \dots, i_r\) のすぐ左には \(1\) つずつ，選んでいないティーポットが存在する．これらを取り除くことで，SIMPLE での任意の選び方が再現できる．

以上より一対一対応がとれる．問題 SIMPLE の答えは \(\mathrm{binom}(N-(r-1),r)\) (\(\mathrm{binom}\) は二項係数) なので，問題 NOADJ の答えも \(\mathrm{binom}(N-(r-1),r)\) である．

以下では，\(\mathrm{noadj}(n, r) := \mathrm{binom}(n-(r-1), r)\) とする．

考察

簡便さのため，ティーポット \(l, \dots, r\) のことをティーポット \([l, r]\) と略記する．

\(a_i \neq -1\) を満たす \(i\) を昇順に \(i_1, \dots, i_k\) とおく．また，便宜上 \(a_0 = 0\), \(i_0 = 0\) とおく．このとき，\(a\) についての条件は以下のように言い換えられる．

  • \(j = 1, \dots, k\) について，ティーポット \([i_{j-1} + 1, i_j]\) のうちちょうど \(a_{i_j} - a_{i_{j-1}}\) 個にコーヒーを入れる．
  • ティーポット \([i_k + 1, N]\) について，コーヒーを入れる個数の制約はない．

このように言い換えた後の制約は，すべてのティーポットをちょうど \(1\) 度ずつカバーする．

ここで，ティーポット \([1, i_{j-1}]\) の満たし方の個数からティーポット \([1, i_{j}]\) の満たし方の個数を求めることを考える．

  • ティーポット \([1, i_{j-1}]\) の満たし方であって，ティーポット \(i_{j-1}\) にコーヒーを入れないものの個数を \(x_0\)
  • ティーポット \([1, i_{j-1}]\) の満たし方であって，ティーポット \(i_{j-1}\) にコーヒーを入れるものの個数を \(x_1\)
  • ティーポット \([1, i_{j}]\) の満たし方であって，ティーポット \(i_{j}\) にコーヒーを入れないものの個数を \(y_0\)
  • ティーポット \([1, i_{j}]\) の満たし方であって，ティーポット \(i_{j}\) にコーヒーを入れるものの個数を \(y_1\)

とする(\(j=1\) のとき，\(x_0=1\), \(x_1=0\))．このとき，これらのあいだの関係は

\[\begin{bmatrix} x_0 & x_1 \\ \end{bmatrix} \begin{bmatrix} f_{0,0}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) & f_{0,1}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) \\ f_{1,0}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) & f_{1,1}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) \\ \end{bmatrix} = \begin{bmatrix} y_0 & y_1 \\ \end{bmatrix}\]

の形で書ける．ここで \(f_{s, t}(n, r)\) は，長さ \(n\) のティーポット列にちょうど \(r\) 個のコーヒーを入れる場合の \(x_s\) から \(y_t\) への寄与であり，

  • \(f_{0,0}(n, r) = \mathrm{noadj}(n-1, r)\)
  • \(f_{0,1}(n, r) = \begin{cases} \mathrm{noadj}(0, r-1) & (n=1) \\ \mathrm{noadj}(n-2, r-1) & (n \geq 2)\end{cases}\)
  • \(f_{1,0}(n, r) = \begin{cases} \mathrm{noadj}(0, r) & (n=1) \\ \mathrm{noadj}(n-2, r) & (n \geq 2)\end{cases}\)
  • \(f_{1,1}(n, r) = \begin{cases} 0 & (n=1) \\ \mathrm{noadj}(0, r-1) & (n=2) \\ \mathrm{noadj}(n-3, r-1) & (n \geq 3)\end{cases}\)

で得られる．これを \(\bm{f}(n, r)\) と表すことにする．

また，ティーポット \([1, i_{k}]\) の満たし方の個数から全体の満たし方の個数を求めることを考えると，

  • ティーポット \([1, i_{k}]\) の満たし方であって，ティーポット \(i_{k}\) にコーヒーを入れないものの個数を \(x_0\)
  • ティーポット \([1, i_{k}]\) の満たし方であって，ティーポット \(i_{k}\) にコーヒーを入れるものの個数を \(x_1\)

としたとき，求める値は \(x_0 \cdot fib[N - i_k] + x_1 \cdot fib[\max(N - i_k - 1, 0)]\) となる，ここで，\(fib[i]\) は

\[fib[i] = \begin{cases} 1 & (i = 0) \\ 2 & (i = 1) \\ fib[i-1]+fib[i-2] & (i \geq 2) \end{cases}\]

という漸化式で得られる値である．

したがって，\(\bm{M} = \Pi_{j=1}^{k} \bm{f}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}})\) の値が求まれば，答えは \(M_{0,0} \cdot fib[N - i_k] + M_{0,1} \cdot fib[\max(N - i_k - 1, 0)]\) で得られる．

クエリごとの更新

行列の列 \(F = (F_1, \dots, F_N)\) をもち，以下の状態を保つことを考える．

  • \(a_i = -1\) の場合，\(F_i\) には単位行列 \(\bm{E} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\) をおく．
  • \(a_i \neq -1\) の場合，\(F_i\) には \(\bm{f}(i - i', a_i - a_{i'})\) をおく．ここで，\(i'\) は以下を満たす最大の整数である．また，便宜上 \(i'=0\) のときは \(a_{i'} = 0\) とする．
    • \(i' < i\)
    • \(a_{i'} \neq -1\) または \(i' = 0\)

このとき，\(\prod_{i=1}^{N} F_i\) は上で求めたい行列 \(\bm{M}\) に一致する．

\(a_{x}\) を変更するとき，以下の値を求めれば，\(F\) のうち更新するべき箇所は \(i = x,\ x_{high}\) に限られる．

  • 以下を満たす最大の整数 \(x_{low}\)
    • \(x_{low} < x\)
    • \(a_{x_{low}} \neq -1\) または \(x_{low} = 0\)
  • 以下を満たす最小の整数 \(x_{high}\)
    • \(x_{high} > x\)
    • \(a_{x_{high}} \neq -1\) または \(x_{high} = N+1\)

平衡二分探索木，あるいはセグメント木を使うことで，\(x_{low}, x_{high}\) を \(O(\log N)\) 時間で求めることができる．

また，\(F\) の一点更新および \(\prod_{i=1}^{N} F_i\) の算出は，セグメント木を使うことでそれぞれ \(O(\log N)\) 時間で実現できる．

したがって，前計算 \(O(N)\), クエリあたり \(O(\log N)\) の時間計算量でこの問題を解くことができた．

実装例 (C++)

C++ であれば，標準ライブラリの std::set によって平衡二分探索木を，AtCoder Library の atcoder::segtree によってセグメント木を実装できる．

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
using std::set;
using std::map;

#include <atcoder/all>
using mint = atcoder::modint998244353;
using atcoder::segtree;

typedef long long int ll;

vector<mint> frac, invf;
void f_init (ll n) {
	frac.resize(n+1);
	invf.resize(n+1);
	frac[0] = 1;
	for (ll i = 1; i <= n; i++) {
		frac[i] = frac[i-1] * i;
	}
	invf[n] = frac[n].inv();
	for (ll i = n; i >= 1; i--) {
		invf[i-1] = invf[i] * i;
	}
}
mint ncr (ll n, ll r) {
	if (n < r || n < 0 || r < 0) return 0;

	if (frac.size() <= n) {
		f_init(n+5);
	}
	return frac[n] * invf[n-r] * invf[r];
}

ll n, q;

using Mat = array<array<mint, 2>, 2>;
const Mat unity = {
	(array<mint, 2>){1,0},
	(array<mint, 2>){0,1}
};
Mat operator* (const Mat &l, const Mat &r) {
	Mat x = {
		(array<mint, 2>){0,0},
		(array<mint, 2>){0,0}
	};
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				x[i][j] += l[i][k] * r[k][j];
			}
		}
	}
	return x;
}

Mat seg_op (Mat l, Mat r) {
	return l * r;
}
Mat seg_e (void) {
	return unity;
}

// n boxes, r balls into unique boxes, no adjacent boxes
mint noadj (ll n, ll r) {
	if (n < r || r < 0) return 0;
	return ncr((n + 1) - r, r);
}

Mat lenmat (ll n, ll r) {
	Mat x;
	x[0][0] = noadj(n-1, r);
	if (n == 1) {
		x[0][1] = noadj(0, r-1);
	} else {
		x[0][1] = noadj(n-2, r-1);
	}
	if (n == 1) {
		x[1][0] = noadj(0, r);
	} else {
		x[1][0] = noadj(n-2, r);
	}
	if (n == 1) {
		x[1][1] = 0;
	} else if (n == 2) {
		x[1][1] = noadj(0, r-1);
	} else {
		x[1][1] = noadj(n-3, r-1);
	}
	
	return x;
}

map<ll, ll> stidx; // set of i such that a_i != -1
void solve () {
	segtree<Mat, seg_op, seg_e> seg(n);

	vector<mint> fib(n+1);
	fib[0] = 1;
	fib[1] = 2;
	for (ll i = 2; i <= n; i++) {
		fib[i] = fib[i-2] + fib[i-1];
	}

	stidx.insert({-1, 0}); // bottom
	stidx.insert({n, n}); // top
	for (ll qi = 0; qi < q; qi++) {
		ll x, y;
		cin >> x >> y;
		--x;

		// erase
		{
			auto it = stidx.find(x);
			if (it != stidx.end()) {
				--it; ll ilow  = (*it).first, vlow  = (*it).second; ++it;
				++it; ll ihigh = (*it).first, vhigh = (*it).second; --it;

				stidx.erase(it);
				seg.set(x, unity);
				if (ihigh < n) seg.set(ihigh, lenmat(ihigh - ilow, vhigh - vlow));
				
			}
		}

		// add
		if (y != -1) {
			stidx.insert({x, y});
			auto it = stidx.find(x);
			--it; ll ilow  = (*it).first, vlow  = (*it).second; ++it;
			++it; ll ihigh = (*it).first, vhigh = (*it).second; --it;

			seg.set(x, lenmat(x - ilow, y - vlow));
			if (ihigh < n) seg.set(ihigh, lenmat(ihigh - x, vhigh - y));
		}

		// answer
		Mat whole = seg.all_prod();
		ll remain;
		{
			auto it = stidx.find(n);
			--it; ll idx = (*it).first;

			remain = (n-1) - idx;
		}
		mint ans = 0;
		ans += whole[0][0] * fib[remain];
		ans += whole[0][1] * fib[max(remain - 1, 0LL)];


		cout << ans.val() << "\n";
	}
	
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q;

	solve();

	return 0;
}

posted:
last update: