問題文

長さ N の正整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． 以降，S=\sum_{1 \leq i \leq N} A_i とおきます．

長さ S の整数列 x は以下の条件をすべて満たすとき（そしてそのときのみ）good であると言います．

• x の各要素は 1 以上 N 以下
• 各整数 i (1 \leq i \leq N) について，x はちょうど A_i 個の i を含む

整数列 x=(x_1,x_2,\cdots,x_S) に対し，x_i>x_{i+1} を満たす index i の個数を f(x) と表すことにします．

good な整数列 x を一様ランダムにとるときの f(x) の期待値を \pmod{998244353} で求めてください．

制約

• 2 \leq N \leq 250000
• 1 \leq A_i
• \sum_{1 \leq i \leq N} A_i < 998244353
• 入力される値はすべて整数

入力例 1

2
1 2

出力例 1

665496236

good な x は以下の 3 通りです．

• x=(1,2,2): f(x)=0
• x=(2,1,2): f(x)=1
• x=(2,2,1): f(x)=1

よって f(x) の期待値は 2/3 です．

入力例 2

5
1 1 1 1 1

出力例 2

2

入力例 3

2
2024 824

出力例 3

841217737

入力例 4

10
19237224 3435339 227368010 836006 153314679 115537801 189694444 76016030 159566203 53238564

出力例 4

873203747

問題文

整数 N が与えられます．

集合 S を S=\{1,2,\cdots,N\} で初期化します． その後，S が空になるまで次の操作を繰り返します．

• S の要素を一様ランダムに 1 つ選び，それを v とおく． S から v の倍数をすべて削除する．

操作回数の期待値を \pmod{998244353} で求めてください．

制約

• 1 \leq N \leq 10^{10}
• 入力される値はすべて整数

入力例 1

2

出力例 1

499122178

操作回数の期待値は 3/2 です．

入力例 2

6

出力例 2

582309209

入力例 3

23

出力例 3

515759591

入力例 4

5000000000

出力例 4

64399530

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) と整数 K が与えられます．

あなたは A のコピーを K 個並べて連結し，長さ NK の整数列 x=(x_1,x_2,\cdots,x_{NK}) を得ました．

あなたはこれから次の操作をちょうど 1 回行います．

• x の（連続とは限らない）（空でもよい）部分列を選び，その要素を逆順に並べ替える． より正確に述べれば，index の列 1 \leq i_1<i_2<\cdots<i_s \leq NK (列の長さ s も任意) を選び，各 1 \leq j \leq s に対して x_{i_j} の値を x_{i_{s-j+1}} で置き換える． この置き換えはすべて同時に行われる．

操作後の x としてありうる数列の個数を 998244353 で割ったあまりを求めてください．

制約

• 1 \leq N \leq 300
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq N
• 入力される値はすべて整数

入力例 1

2 2
1 2

出力例 1

6

この例では，x=(1,2,1,2) です． 操作後の x としてあり得る数列は以下の 6 通りです．

• (1,2,1,2) : s=1, (i_1)=(1) とすればよい．
• (2,1,1,2) : s=2, (i_1,i_2)=(1,2) とすればよい．
• (1,1,2,2) : s=2, (i_1,i_2)=(2,3) とすればよい．
• (1,2,2,1) : s=2, (i_1,i_2)=(3,4) とすればよい．
• (2,2,1,1) : s=2, (i_1,i_2)=(1,4) とすればよい．
• (2,1,2,1) : s=4, (i_1,i_2,i_3,i_4)=(1,2,3,4) とすればよい．

入力例 2

3 2
3 3 3

出力例 2

1

入力例 3

5 3
1 2 3 4 5

出力例 3

9216

入力例 4

30 1000000000000
8 3 8 10 1 5 3 1 6 4 3 6 2 6 6 9 5 5 8 3 3 4 10 2 3 2 8 10 8 1

出力例 4

401626004

問題文

数列 a=(a_1,a_2,\cdots,a_k) に対し，f(a) を以下のように定めます．

• f(a)=\sum_{1 \leq i \leq k} \min(a_1,a_2,\cdots,a_i)

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

整数列 A を 2 つの（連続とは限らない）（空でもよい）部分列に分解し，それらを X_1,X_2 とおきます． 分解の際，A の各要素がちょうど 1 つの部分列に含まれるようにします． f(X_1)+f(X_2) としてありうる最大値を求めてください．

制約

• 1 \leq N \leq 500000
• 1 \leq A_i \leq 10^9
• 入力される値はすべて整数

入力例 1

6
5 3 6 1 4 7

出力例 1

23

例えば，X_1=(5,3,1),X_2=(6,4,7) と分解すると，f(X_1)+f(X_2)=9+14=23 になります． 23 より大きい値は達成できないため，これが答えです．

入力例 2

10
22 7 20 26 1 11 7 1 15 10

出力例 2

104

入力例 3

15
140039457 164832983 239276621 245532751 274195604 320064892 499774361 419370025 249168130 521915711 744280520 561032101 857077284 543856068 910500852

出力例 3

4618736183

入力例 4

20
596982638 713892371 987307025 722757772 759622047 853214705 628902494 623807668 755031424 486834509 272961036 423817262 434140395 284114341 88860862 222135106 69837030 210989591 225447688 86416231

出力例 4

9047041486

問題文

1 から N までの番号のついた N 頂点からなる根付き木 T があります． 根は頂点 1 で，頂点 i (2 \leq i \leq N) の親は頂点 P_i (P_i<i) です． この木の辺は有向辺で，各辺は親から子の方向へ向いています．

あなたは T に M 本の辺を追加し，有向グラフ G を作りました． i 番目に追加した辺は，頂点 A_i から頂点 B_i へ向かう辺でした． ここで，A_i,B_i は以下の条件を満たすことが保証されます．

• 1 \leq B_i<A_i \leq N
• T において頂点 A_i は頂点 B_i の子孫である
• T において頂点 A_i は葉でない

なお，同じ辺を複数本追加することもありえます．

あなたはこれから G の頂点 1 からスタートし，停止するまで次の操作を繰り返します．

• 今いる頂点から出る辺が存在しないなら停止する．
• 今いる頂点から出る辺が存在するなら，そのうちの 1 つを一様ランダムに選び，その辺が向かう頂点へ移動する．

停止するまでに移動する回数の期待値を\pmod{P} で求めてください．

ただしこの問題では P の値は入力で与えられません． そのかわり，以下の制約をすべて満たすような P をあなたが選び，その P に対して問題を解いてください．

• P は素数
• 998244353 \leq P < 2 \times 10^9
• \pmod{P} で答えが定義できる

制約

• 2 \leq N \leq 250000
• 0 \leq M \leq 250000
• 1 \leq P_i < i
• 1 \leq B_i<A_i \leq N
• T において頂点 A_i は頂点 B_i の子孫である
• T において頂点 A_i は葉でない
• 入力される値はすべて整数
• サンプル以外のテストケースは 50 個以下である．

入力例 1

3 0
1 2

出力例 1

2 998244353

入力例 2

3 1
1 2
2 1

出力例 2

4 998244353

入力例 3

7 5
1 2 2 4 4 3
3 1
2 1
3 2
4 2
3 2

出力例 3

453747441 998244353

入力例 4

20 25
1 2 3 2 5 2 6 1 9 2 2 12 13 1 2 16 17 16 19
13 12
12 1
17 1
6 5
5 1
13 12
12 2
17 16
17 16
17 16
19 16
6 5
16 2
6 5
9 1
9 1
13 12
13 12
6 5
19 16
6 5
17 16
6 5
13 1
13 12

出力例 4

529789893 998244353

問題文

1 から N までの番号がついた N 頂点からなる DAG が与えられます． 辺は M 本あり，i 番目の辺は頂点 U_i から頂点 V_i に向かう辺です． ここで，U_i<V_i が保証されます． 各頂点には整数が書かれており，頂点 i には整数 A_i が書かれています．

頂点の部分集合 s に対し，f(s) を以下のように定めます．

• f(s)=\sum_{v \in s} \min\{A_u\ |\ u \in s かつ DAG において頂点 u から頂点 v へ移動できる \}

各整数 K=1,2,\cdots,N について，以下の問題に答えてください．

頂点集合 \{1,2,\cdots,N\} を K 個の (空でもよい) 部分集合に分解し，それらを X_1,X_2,\cdots,X_K とおきます． 分解の際，各頂点がちょうど 1 つの部分集合に含まれるようにします． \sum_{1 \leq i \leq K}f(X_i) としてありうる最大値を求めてください．

制約

• 1 \leq N \leq 80
• 0 \leq M \leq 160
• 1 \leq A_i \leq 80
• 1 \leq U_i < V_i \leq N
• (U_i,V_i) \neq (U_j,V_j) (i \neq j)
• 入力される値はすべて整数

入力例 1

4 4
1 2 3 4
1 2
1 3
2 4
3 4

出力例 1

4 8 10 10

各 K に対する最適解（の一例）は以下のとおりです．

• K=1 : X_1=\{1,2,3,4\}
• K=2 : X_1=\{1\},X_2=\{2,3,4\}
• K=3 : X_1=\{1\},X_2=\{2,3\},X_3=\{4\}
• K=4 : X_1=\{1\},X_2=\{2\},X_3=\{3\},X_4=\{4\}

入力例 2

10 9
22 7 20 26 1 11 7 1 15 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

出力例 2

49 104 120 120 120 120 120 120 120 120

入力例 3

15 13
20 12 14 20 22 20 26 34 40 42 44 60 45 69 73
1 14
2 5
2 8
2 9
2 12
2 15
4 7
6 12
7 9
8 15
10 15
11 12
13 14

出力例 3

317 513 541 541 541 541 541 541 541 541 541 541 541 541 541

入力例 4

20 31
54 12 12 26 7 6 38 51 29 52 70 49 67 65 80 67 54 77 74 73
1 2
2 3
3 4
1 5
2 6
5 6
3 7
6 7
4 8
7 8
5 9
6 10
9 10
7 11
10 11
8 12
11 12
9 13
10 14
13 14
11 15
14 15
12 16
15 16
13 17
14 18
17 18
15 19
18 19
16 20
19 20

出力例 4

190 749 872 935 961 963 963 963 963 963 963 963 963 963 963 963 963 963 963 963