本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-27 13:57:34

[ABC246C] Coupon

题面翻译

商店里有 $N$ 件商品，第 $i$ 件物品价格 $A_i$ 元。

有 $K$ 张优惠券，一个优惠券可以用于一个物品上，同一个物品可以使用若干张优惠券（可能不使用优惠券）。

一张优惠券可以降低价格 $X$ 元，在 $a$ 元的物品上使用 $k$ 张优惠券后的价格降低为 $\max{a - kX, 0 }$ 元。

请求出买下所有物品的最少价格。

题目描述

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ K $

$ X $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

5 4 7
8 3 10 5 13

样例输出 #1

12

样例 #2

样例输入 #2

5 100 7
8 3 10 5 13

样例输出 #2

0

样例 #3

样例输入 #3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

样例输出 #3

112

提示

制約

• $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
• $ 1\ \leq\ K,\ X\ \leq\ 10^9 $
• $ 1\ \leq\ A_i\ \leq\ 10^9 $
• 入力はすべて整数

Sample Explanation 1

$ 1 $ 番目の商品に対してクーポン $ 1 $ 枚、$ 3 $ 番目の商品に対してクーポン $ 1 $ 枚、$ 5 $ 番目の商品に対してクーポン $ 2 $ 枚を使用すると、 - $ 1 $ 番目の商品を $ \max\lbrace\ A_1-X,\ 0\ \rbrace\ =\ 1 $ 円で買うことができ、 - $ 2 $ 番目の商品を $ \max\lbrace\ A_2,\ 0\ \rbrace\ =\ 3 $ 円で買うことができ、 - $ 3 $ 番目の商品を $ \max\lbrace\ A_3-X,\ 0\ \rbrace\ =\ 3 $ 円で買うことができ、 - $ 4 $ 番目の商品を $ \max\lbrace\ A_4,\ 0\ \rbrace\ =\ 5 $ 円で買うことができ、 - $ 5 $ 番目の商品を $ \max\lbrace\ A_5-2X,\ 0\ \rbrace\ =\ 0 $ 円で買うことができます。 よって、すべての商品を $ 1\ +\ 3\ +\ 3\ +\ 5\ +\ 0\ =\ 12 $ 円で買うことができ、これが最小です。

[ABC246D] 2-variable Function

题面翻译

给定整数 $N$，请你找到最小的整数 $X$，满足：

• $X \ge N$
• 存在一对非负整数 $(a, b)$，使得 $X = a^3 + a^2b + ab^2 + b^3$。

题目描述

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

答えを整数として出力せよ。

样例 #1

样例输入 #1

9

样例输出 #1

15

样例 #2

样例输入 #2

0

样例输出 #2

0

样例 #3

样例输入 #3

999999999989449206

样例输出 #3

1000000000000000000

提示

制約

• $ N $ は整数
• $ 0\ \le\ N\ \le\ 10^{18} $

Sample Explanation 1

$ 9\ \le\ X\ \le\ 14 $ であるようなどの整数 $ X $ についても、問題文中の条件を満たすような $ (a,b) $ は存在しません。 $ X=15 $ は $ (a,b)=(2,1) $ とすると問題文中の条件を満たします。

Sample Explanation 2

$ N $ 自身が条件を満たすこともあります。

Sample Explanation 3

入出力が $ 32 $bit 整数型に収まらない場合があります。

[ABC263E] Sugoroku 3

题面翻译

题目描述

一共有 $N$ 个格子编号 $1$ 到 $N$。有一个人站在 $1$ 号格子。

对于 $\forall i \in [1,N-1]$ 号格子有一个 $A_i + 1$ 面的骰子，写有 $0$ 到 $A_i$ 这些数。如果 ta 掷到了 $k$，他将往前走 $k$ 格，走到 $i+k$ 号方格。

求走到 $N$ 号方格的期望次数。对 $998244353$ 取模。

输入格式

第一行一个正整数 $N$，第二行 $N-1$ 个正整数表示 $A_i$。

输出格式

如果期望次数为 $\frac{P}{Q}$，输入最小非负整数 $R$ 使得 $R\times Q \equiv P\pmod {998244353}$。

数据范围

$2\leq N\leq 2\times 10^5$

$\forall i \in [1,N-1],1\leq A_i\leq N-i$

题目描述

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{N-1} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3
1 1

样例输出 #1

4

样例 #2

样例输入 #2

5
3 1 2 1

样例输出 #2

332748122

提示

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、$ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。

制約

• $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $
• $ 1\ \le\ A_i\ \le\ N-i(1\ \le\ i\ \le\ N-1) $
• 入力は全て整数。

Sample Explanation 1

求める期待値は $ 4 $ であるため、$ 4 $ を出力します。 マス $ N $ に到達するまでの流れとしては、以下のようなものが考えられます。 - マス $ 1 $ で $ 1 $ を出し、マス $ 2 $ に移動する。 - マス $ 2 $ で $ 0 $ を出し、移動しない。 - マス $ 2 $ で $ 1 $ を出し、マス $ 3 $ に移動する。 このようになる確率は $ \frac{1}{8} $ です。

[ABC246F] typewriter

题面翻译

给定 $ n $ 个字符串，字符集为小写字母，可以任意选择一个字符串，作为字符库，然后（可多次选择同一字符）任意组成长度为 $ l $ 的字符串，求一共能形成多少种长度为 $ l $ 的字符串。

请输出方案数模 $998244353$。

题目描述

$ N $ 段からなるタイプライターがあります。このうち、上から $ i $ 段目のキーでは文字列 $ S_i $ に含まれる文字が打てます。

このキーボードを使って、以下のルールで文字列をひとつ入力することを考えます。

• まず、整数 $ 1\ \le\ k\ \le\ N $ を選択する。
• その後、空文字列から始めて、上から $ k $ 段目にあるキーだけを使ってちょうど $ L $ 文字の文字列を入力する。

このルールに従って入力可能な $ L $ 文字の文字列は何通りありますか？ 答えは非常に大きくなる場合があるので $ 998244353 $ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ L $ $ S_1 $ $ S_2 $ $ \dots $ $ S_N $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

2 2
ab
ac

样例输出 #1

7

样例 #2

样例输入 #2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

样例输出 #2

1352

样例 #3

样例输入 #3

5 1000000000
abc
acde
cefg
abcfh
dghi

样例输出 #3

346462871

提示

制約

• $ N,L $ は整数
• $ 1\ \le\ N\ \le\ 18 $
• $ 1\ \le\ L\ \le\ 10^9 $
• $ S_i $ は abcdefghijklmnopqrstuvwxyz の(連続とは限らない)空でない部分列

Sample Explanation 1

入力可能な文字列は aa, ab, ac, ba, bb, ca, cc の $ 7 $ つです。

Sample Explanation 3

答えを $ 998244353 $ で割った余りを出力してください。

[ABC246G] Game on Tree 3

题面翻译

给定一棵树，有点权，B 初始在 $ 1 $，每轮 A 选择一个点将权值变为 $ 0 $，然后 B 移动一次，B 可在任意时刻停止游戏然后获得所在点上的权值的得分，两人均采取最优策略那么最终 B 最少会拿到多少的得分。

题目描述

$ N $ 個の頂点を持ち、頂点 $ 1 $ を根とする根付き木があります。 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、$ i $ 本目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結びます。 また、根以外の頂点には正の整数が書かれており、具体的には、$ i\ =\ 2,\ 3,\ \ldots,\ N $ について、頂点 $ i $ に正の整数 $ A_i $ が書かれています。 高橋君と青木君はこの根付き木と $ 1 $ 個のコマを使って次の対戦ゲームをします。

はじめ、頂点 $ 1 $ にコマが置かれています。その後、ゲームが終了するまで下記の手順を繰り返します。

1. まず、青木君が根以外の頂点を任意に $ 1 $ 個選び、その頂点に書かれた整数を $ 0 $ に書き換える。
2. 次に、高橋君がコマを、いまコマがある頂点の（直接の）子のいずれかに移動する。
3. その後、コマが葉にある場合はゲームが終了する。そうでない場合であっても、高橋君は望むならゲームを直ちに終了させることができる。

ゲーム終了時点でコマがある頂点に、ゲーム終了時点で書かれている整数が、高橋君の得点となります。 高橋君は自身の得点を出来るだけ大きく、青木君は高橋君の得点を出来るだけ小さくしたいです。 両者がそのために最適な行動を取るときの高橋君の得点を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_2 $ $ \ldots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \dots $ $ u_{N-1} $ $ v_{N-1} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

样例输出 #1

5

样例 #2

样例输入 #2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

样例输出 #2

70

提示

制約

• $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
• $ 1\ \leq\ A_i\ \leq\ 10^9 $
• $ 1\ \leq\ u_i,\ v_i\ \leq\ N $
• 与えられるグラフは木である。
• 入力はすべて整数

Sample Explanation 1

両者が最適な行動をとる場合のゲームの進行の一例として次のものがあります。 1. はじめ、コマは頂点 $ 1 $ に置かれています。 2. 青木君が頂点 $ 7 $ に書かれた整数を $ 10 $ から $ 0 $ に書き換えます。 3. 高橋君がコマを頂点 $ 1 $ から頂点 $ 2 $ に動かします。 4. 青木君が頂点 $ 4 $ に書かれた整数を $ 6 $ から $ 0 $ に書き換えます。 5. 高橋君がコマを頂点 $ 2 $ から頂点 $ 5 $ に動かします。 6. 高橋君がゲームを終了します。 ゲーム終了時点でコマは頂点 $ 5 $ にあり、頂点 $ 5 $ にはゲーム終了時点で整数 $ 5 $ が書かれているので、高橋君の得点は $ 5 $ です。