No.1262 グラフを作ろう！

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 :

PCTprobability / テスター :

nok0

3 ProblemId : 5021 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-10-16 22:30:10

正整数 $N, M$ と長さが $M$ の正数列 $A$ が与えられます。

以下の方法で関数 $f (a, b)$ を定義します。

頂点に $0, 1, . . ., N - 1$ の番号がついた $N$ 頂点を用意し、変数 $X := a - 1, Y := (X - b) m o d a$ とします。そして以下の操作を行います。

このとき $\sum_{i = 0}^{M - 1} \sum_{j = 1}^{A_{i}} f (A_{i}, j)$ を求めてください。

 $N$   $M$ 
 $A_{0}$   $A_{1}$  ... $A_{M - 1}$

・入力は全て整数である。
・ $1 \leq N, M \leq 10^{6}$
・ $1 \leq A_{i} \leq N$

$\sum_{i = 0}^{M - 1} \sum_{j = 1}^{A_{i}} f (A_{i}, j)$ を求めてください。最後に改行してください。

3 1
3

$f (3, 1) + f (3, 2) + f (3, 3)$ を求めます。 $f (3, 1)$ を考えます。

始め $x = 2, y = 1$ です。ここで頂点 $2$ と頂点 $1$ を結びます。まだ頂点 $2$ を始点、終点とする閉路はないので操作を続けます。
$x = 1, y = 0$ となっています。頂点 $1$ と頂点 $0$ を結びます。まだ頂点 $2$ を始点、終点とする閉路はないので操作を続けます。
$x = 0, y = 2$ となっています。頂点 $0$ と頂点 $2$ を結びます。ここで頂点 $2$ を始点、終点とする閉路が生まれ、その閉路に含まれる最小の頂点番号は $0$ なので $f (3, 1) = 0$ となります。

100 5
23 34 54 99 57

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。