実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺からなる単純で連結な無向グラフがあります． 頂点には 1 から N までの番号がついており， i 番目の辺は頂点 A_i と頂点 B_i を結んでいます．
(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) であって，以下の条件を満たすものの個数を 998244353 で割った余りを求めてください．
- 頂点集合の（非空な）部分集合 S であって，S による誘導部分グラフが連結になるものを考える． この時，S に含まれる頂点 v のうち，番号が最大であるものは，P_v の値も最大である． つまり，\max\{v|v \in S\}=\argmax\{P_v|v \in S\} である．
誘導部分グラフとは
S をグラフ G の頂点の部分集合とします． このとき，G の S による誘導部分グラフとは，頂点集合が S で，辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです．
制約
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq N
- 与えられるグラフは単純（自己ループや多重辺を含まない）かつ連結である
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを出力せよ．
入力例 1
4 4 1 2 2 4 4 1 3 4
出力例 1
3
条件を満たす順列は P=(1,2,3,4),(1,3,2,4),(2,3,1,4) です．
逆に，P=(2,1,3,4) などは条件を満たしません． これは例えば，S=\{1,2\} とすると，S の中で番号最大の頂点は v=2 であるのに対し，P_v が最大となるのは v=1 だからです．
入力例 2
10 10 4 8 1 3 6 10 6 7 8 7 1 5 4 2 5 2 3 9 9 10
出力例 2
126
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．
あなたは以下の 2 種類の操作を好きな順序で好きな回数 (0 回でもよい) 繰り返すことができます．
- 操作 1: A の先頭の要素に 1 を足す．つまり，A_1:=A_1+1 とする．
- 操作 2: A の先頭の要素を末尾に移動する．つまり，A:=(A_2,A_3,\cdots,A_N,A_1) とする．
あなたの目標は，A を広義単調増加 (A_1 \leq A_2 \leq \cdots \leq A_N) にすることです． 目標達成のために必要な操作回数の最小値を求めてください．
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
答えを出力せよ．
入力例 1
4 2 4 1 3
出力例 1
3
以下のように操作すればよいです．
- 操作 1 を行う．A=(3,4,1,3) になる．
- 操作 2 を行う．A=(4,1,3,3) になる．
- 操作 2 を行う．A=(1,3,3,4) になる．
入力例 2
20 786820955 250480341 710671230 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280521 249168130
出力例 2
3774454944
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
1 と 2 からなる長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．
A を K 個の連続部分列に分割することを考えます． この時，各部分列について，その値の総和が 3 で割り切れないようにしたいです．
このような分割が可能かどうか判定し，可能な場合は分割の方法を一つ示してください．
制約
- 2 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 2
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 \cdots A_N
出力
条件を満たす分割が存在しない場合，No と出力せよ．
存在する場合，以下の形式で答えを出力せよ．
Yes L_1 L_2 \cdots L_K
ここで，L_i は先頭から i 番目の部分列の長さを表す． より正確には，各 i について，A の先頭から (\sum_{1 \leq j<i}L_j)+1 番目の要素から \sum_{1 \leq j \leq i}L_j 番目の要素までを含む連続部分列を取り出すことを意味する． L は，1 \leq L_i および \sum_{1 \leq i \leq K}L_i=N を満たす必要がある．
解が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
4 2 1 2 2 1
出力例 1
Yes 1 3
例えば，A を (1),(2,2,1) と分割すれば条件を満たします．
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
整数 N が与えられます．
非負整数列 A=(A_1,A_2,\cdots,A_k) であって，以下の条件を満たすものが存在するか判定してください． また，存在するならば実際に一つ示してください．
- A の長さ k は 1 以上 100 以下である．
- A の各要素は 0 以上 2^{20}-1 以下の整数である．
- A の非空な（連続するとは限らない）部分列であって，その値のビット単位 \mathrm{AND} が 0 になるものを考える． そのような部分列の個数はちょうど N 個である． ただしここで，取り出す位置が異なる 2 つの部分列は，値が同じであったとしても異なるものとして扱う．
ビット単位 \mathrm{AND} 演算とは
整数 A, B のビット単位 \mathrm{AND}、A\ \mathrm{AND}\ B は以下のように定義されます。
- A\ \mathrm{AND}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{AND} は (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
出力
条件を満たす数列 A が存在しない場合，-1 と出力せよ．
存在する場合，以下の形式で出力せよ．
k A_1 A_2 \cdots A_k
条件をみたす解が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
3
出力例 1
3 2 1 1
A の非空な部分列であって，その値のビット単位 \mathrm{AND} が 0 になるものは，以下の 3 つです．
- (2,1) (1,2 番目の要素を取り出した)
- (2,1) (1,3 番目の要素を取り出した)
- (2,1,1) (1,2,3 番目の要素を取り出した)
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
長さ 2^L の円周があります． 円周上のある点から距離 x 時計回りに進んだ点を，座標 x の点と呼ぶことにします．
円周上で N 個の寿司が動いています． i 番目の寿司は時刻 0 に座標 A_i にあり，時計回りに速度 V_i で動いています． また，i 番目の寿司の価値は W_i です．
あなたはこれから非負実数 t を選びます． そして，時刻 t に座標 0 に存在するすべての寿司を獲得します．
あなたが獲得する寿司の価値の総和としてありうる最大値を求めてください．
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L \leq 30
- 0 \leq A_i < 2^L
- 1 \leq V_i < 2^L
- 1 \leq W_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N L A_1 V_1 W_1 A_2 V_2 W_2 \vdots A_N V_N W_N
出力
答えを出力せよ．
入力例 1
3 2 3 1 1 2 2 2 1 1 3
出力例 1
5
例えば t=3 を選ぶと，2 番目と 3 番目の寿司を獲得でき，その価値の総和は 5 です．
入力例 2
20 4 12 10 946667801 0 2 520643153 5 2 543856068 8 8 419370025 11 5 910500853 2 3 715892722 15 8 459924868 4 8 950300099 7 2 504976377 11 1 152036485 15 4 361324668 7 14 628902494 12 12 69837030 7 7 596982638 1 10 222135106 3 14 210989591 13 6 935147464 13 2 362117198 11 4 909241708 1 8 487330736
出力例 2
1705145758
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 1300 点
問題文
1 から N までの番号のついた N 台のサーバーがあります． すぬけくんは，秘伝のレシピをサーバー 1 に保存しました． 他のサーバーにはレシピは保存されていません．
これから N(N-1)/2 回，すぬけくんは以下の操作を行います．
- 相異なる 2 つのサーバーを選ぶ． ただし，選ぶサーバーの組は，今まで選んだことのない組でなければならない． なお，組 (x,y) は組 (y,x) と同一とみなす． 操作前の段階で少なくとも一方のサーバーがレシピを保存している場合，操作後には両方のサーバーにレシピが保存される．
操作を行う方法は，(N(N-1)/2)! 通りあります． このうち，以下の条件を満たす方法が何通りあるかを 998244353 で割った余りを求めてください．
- 各 i=2,3,\cdots,N について，A_i 回目の操作が終わった段階で，サーバー i にレシピが保存されている．
制約
- 2 \leq N \leq 13
- 1 \leq A_i \leq N(N-1)/2
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_2 A_3 \cdots A_N
出力
答えを出力せよ．
入力例 1
3 1 3
出力例 1
2
例えば，以下のような操作は条件を満たします．
- 1 回目の操作: サーバー 1 と 2 を選ぶ．新たにサーバー 2 にレシピが保存される．
- 2 回目の操作: サーバー 2 と 3 を選ぶ．新たにサーバー 3 にレシピが保存される．
- 3 回目の操作: サーバー 1 と 3 を選ぶ．
入力例 2
3 1 1
出力例 2
0
入力例 3
4 1 2 6
出力例 3
48
入力例 4
13 62 20 56 74 2 32 20 2 41 27 22 44
出力例 4
665691201
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 1600 点
問題文
整数 N が与えられます． 1 から N までの番号のついた N 頂点からなる無向グラフ G を考えます． 以下の条件をすべて満たすグラフ G の個数を 998244353 で割った余りを求めてください．
- G は多重辺や自己ループを含まない．
- G は連結である．
- G の頂点集合の分割 \{S_1,S_2,\cdots\} であって，以下の条件をみたすものが存在する．
- 各 S_i について，|S_i| \geq 2 である．
- 各 S_i について，S_i による誘導部分グラフは，連結な二部グラフである．
誘導部分グラフとは
S をグラフ G の頂点の部分集合とします． このとき，G の S による誘導部分グラフとは，頂点集合が S で，辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです．
制約
- 2 \leq N \leq 2 \times 10^5
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
出力
答えを出力せよ．
入力例 1
2
出力例 1
1
入力例 2
3
出力例 2
3
入力例 3
4
出力例 3
38
入力例 4
5
出力例 4
712
入力例 5
12345
出力例 5
503682022