コンテストページ

問題概要

A 問題: Course

実行時間制限: 3 秒 / メモリ制限: 262144 KB

$n$ 頂点の根付き木と長さ $n$ の数列 $s _ 1, s _ 2, \cdots, s _ n$ と $c _ 1, c _ 2, \cdots, c _ n$ が与えられる。 $Q$ 個のクエリに答えよ。

$i$ 番目のクエリでは整数 $w _ i$ が与えられるので、長さ $n$ の非負整数の列 $k _ 1, k _ 2, \cdots, k _ n$ で、以下の条件を満たすものの個数を $998244353$ で割った余りを求めよ。

について、以下が成り立つ。
- $S$ を頂点 $i$ の部分木の頂点の番号の集合とすると、 $\displaystyle{\sum _ {v \in S} (k _ v s _ v) \geq c _ i}$
$\displaystyle{\sum _ {i = 1} ^ N k _ i s _ i = w}$

入力は以下の制約を満たす。

$1 \leq n \leq 100$
$1 \leq Q \leq 10$
$1 \leq s _ i \leq 5 \ (1 \leq i \leq n)$
$0 \leq c_ i \leq 150 \ (1 \leq i \leq n)$
$0 \leq w _ i \leq 10 ^ 8 \ (1 \leq i \leq Q)$

B 問題: Sample Game

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$1$ 以上 $n$ 以下の整数を、 $i \ (1 \leq i \leq n)$ は確率 $\displaystyle{\frac{w _ i}{\displaystyle{\sum _ {i = 1} ^ {n} w _ i}}}$ で生成する乱数生成器がある。

以下の操作を行う。

乱数生成器で整数を $1$ つ生成する。生成した整数を $x$ とおく。
$x$ が今までに生成したすべての整数と比べ等しいまたは大きい場合、1. に戻る。そうでない場合、3. に進む。
生成した整数の個数を $m$ として、 $m ^ 2$ の得点を得る。

得点の期待値を既約分数で表し、 $\mod 998244353$ で出力せよ。ただし、得点の期待値は有理数であることが証明できる。

入力は以下の制約を満たす。

$2 \leq n \leq 100$
$1 \leq w _ i \leq 10 ^ 6 \ (1 \leq i \leq n)$

C 問題: LCS

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$2$ つの文字列 $s _ 1, s _ 2$ に対し、 $LCS(s _ 1, s _ 2)$ を $s _ 1, s _ 2$ の最長共通部分列の長さとする。

整数 $a, b, c, n$ が与えられる。小文字のアルファベットからなる $n$ 文字の文字列 $s _ 1, s _ 2, s _ 3$ であって、 $LCS(s _ 1, s _ 2) = a, LCS(s _ 2, s _ 3) = b, LCS(s _ 1, s _ 3) = c$ となるものを一つ構築するか、条件を満たす文字列が存在しないと報告せよ。

入力は以下の制約を満たす。

$1 \leq n \leq 1000$
$0 \leq a, b, c \leq n$

D 問題: Rebuild Tree

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$n$ 頂点の木が与えられる。木の辺の集合を $T$ とする。また、 $n$ 頂点の完全グラフの辺の集合を $B$ とする。

整数 $k$ が与えられる。以下の条件をすべて満たす集合 $X, Y$ の組の個数を $998244353$ で割った余りを求めよ。

$X \subseteq T$
$Y \subseteq B$
$|X| = n - 1 - k$
$|Y| = k$
辺の集合が $X \cup Y$ である $n$ 頂点のグラフは木である。

入力は以下の制約を満たす。

$2 \leq n \leq 5 \times 10 ^ 4$
$1 \leq k \leq \min(100, n - 1)$

E 問題: Tree Xor

実行時間制限: 2 秒 / メモリ制限: 262144 KB

$\oplus$ をビット単位の排他的論理和とする。

$n$ 頂点の木が与えられる。木の各辺には整数 $c$ が書いてある。また、長さ $n$ の数列 $l _ 1, l _ 2, \cdots, l _ n$ と $r _ 1, r _ 2, \cdots, r _ n$ が与えられる。長さ $n$ の非負整数の列 $w _ 1, w _ 2, \cdots, w _ n$ であって、以下の条件をすべて満たすものの個数を求めよ。

$l _ i \leq w _ i \leq r _ i (1 \leq i \leq n)$
木の各辺 $(u, v)$ に対し、 $w _ u \oplus w _ v = c$ である。

入力は以下の制約を満たす。

$1 \leq n \leq 10 ^ 5$
$0 \leq l _ i \leq r _ i \lt 2 ^ {30}$
$0 \leq c \lt 2 ^ {30}$

F 問題: Just a joke

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$n$ 頂点 $m$ 辺のグラフ $G$ が与えられる。Alice と Bob が以下の操作のうち 1 つを繰り返すゲームをする。操作ができなくなった人が負けである。勝者は誰か求めよ。

$G$ の辺を 1 本選び、それを削除する。
$G$ の連結成分で閉路を含まないものを 1 つ選び、削除する。

入力は以下の制約を満たす。

$1 \leq n \leq 100$
$0 \leq m \leq min(200, \displaystyle{n(n-1)}{2})$

G 問題: Product

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$\displaystyle{\sum _ {i = 1} ^ n a _ i} = D$ である長さ $n$ の非負整数の列 $a _ 1, a _ 2, \cdots. a _ n$ すべてに対する $\displaystyle{\frac{D!}{\prod _ {i = 1} ^ n (a _ i + k)!}}$ の総和を $\mod 998244353$ で求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 50$
$0 \leq k \leq 50$
$0 \leq D \leq 10 ^ 8$

H 問題: Convolution

実行時間制限: 3 秒 / メモリ制限: 262144 KB

$\oplus$ をビット単位の排他的論理和とする。

$p _ i$ を $i$ 番目の素数とする。 $x$ と $y$ が $x = \displaystyle{\prod _ i p _ i ^ {a _ i}}, y = \displaystyle{\prod _ i p _ i ^ {b _ i}}$ と素因数分解されるとき、 $x \otimes y = \displaystyle{\prod _ i p _ i ^ {|a _ i - b _ i|}}$ と定義する。

長さ $n$ の整数の列 $a _ 1, a _ 2, \cdots, a _ n$ と整数 $c$ が与えられる。 $b _ i = \displaystyle{\sum _ {\substack{1 \leq j, k \leq n \\ j \otimes k = i}} a _ j k ^ c}$ としたとき、 $\displaystyle{\bigoplus _ {i = 1, n} (b _ i \mod 998244353)}$ を求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 10 ^ 6$
$0 \leq a _ i \lt 998244353 \ (1 \leq i \leq n)$
$0 \leq c \leq 10 ^ 9$

I 問題: Inverse Pair

実行時間制限: 1 秒 / メモリ制限: 262144 KB

長さ $n$ の数列 $t _ 1, t _ 2, \cdots, t _ n$ の重みを、 $1 \leq i \lt j \leq n, t _ i > t _ j$ となる $(i, j)$ の個数とする。

長さ $n$ の順列 $a _ 1, a _ 2, \cdots, a _ n$ が与えられる。 $b _ i \in \lbrace 0,1 \rbrace$ を満たす長さ $n$ の数列 $b _ 1, b _ 2, \cdots, b _ n$ を選び、 $c _ i = a _ i + b _ i (1 \leq i \leq n)$ としたときの $c$ の重みの最小値を求めよ。