問題文

カニとエビがそれぞれ何匹かいます（いずれかの数が 0 匹である可能性もあります）。

これらの生物の脚の数を数えたところ、合計で N 本でした。このとき、カニは少なくとも何匹いると考えられるでしょうか。

なお、この問題では、1 匹のカニは 8 本か 10 本の脚を持ち、1 匹のエビは 26 本の脚を持つとします。

制約

• 8 \leq N \leq 10^{15}
• 合計の脚の数が N 本であることがあるようなカニとエビの数の組合せが存在する。

部分点

• N \leq 100 を満たすテストケース全てに正解すると、30 点が与えられる。

入力例 1

44

出力例 1

2

この場合、タラバガニ（脚 8 本）、ズワイガニ（脚 10 本）、エビ（脚 26 本）が 1 匹ずついるとするとカニの数は 2 匹ですが、カニの数が 1 匹以下であることはありません。

入力例 2

52

出力例 2

0

エビしかいないかもしれません。

配点 : 100 点

問題文

素数 K が与えられます。 空の数列があり、えびまちゃんはこの末尾に 1 から N までの整数を 1 個ずつ順に追加していきます。

ところで、のいみちゃんは長さ K の等差数列が嫌いです。えびまちゃんが整数 X を数列に追加したことで、部分列（連続とは限らない）として長さ K の等差数列が取れてしまうとき、X を即座に捨ててしまいます。

最終的に数列に含まれる要素の数を求めてください。

制約

• 1 \le N \le 10^{18}
• 2 \le K \le 100
• K は素数

入力例 1

5 2

出力例 1

1

えびまちゃんが 2 以降の整数 X を追加したとき、\left( 1, X \right) という長さ 2 の等差数列が出来てしまいます。

入力例 2

10 3

出力例 2

5

最終的な数列は \left(1, 2, 4, 5, 10\right) です。

問題文

整数 1, 2, \cdots, N が書かれたボールがそれぞれ 2 個ずつ、計 2N 個あります。

これら全てを、互いに区別の付かない K 個の箱に入れます。全ての箱に 1 個以上のボールが入るような入れ方は何通りあるでしょうか。

ただし、同じ整数が書かれたボールは互いに区別が付かず、違う整数が書かれたボールは互いに区別が付くとします。

答えは非常に大きくなる可能性があるので、 998244353 で割った余りを求めてください。

制約

• 1 \leq N,K \leq 200

入力例 1

2 2

出力例 1

4

1,2 が書かれたボールがそれぞれ 2 個ずつあり、箱は 2 個あります。

このとき、 \{\{1,1,2\},\{2\}\},\{\{1,1\},\{2,2\}\},\{\{1,2\},\{1,2\}\},\{\{1\},\{1,2,2\}\} の計 4 通りの入れ方があります。

入力例 2

200 200

出力例 2

968822905

答えを 998244353 で割った余りを求めてください。

配点 : 100 点

問題文

長さ N の整数列 A_1, \ldots, A_N が与えられます。 次の条件を満たす整数の組 \left(i,j \right) \left(1 \le i < j \le N \right) の数を出力してください。

• A_i - A_j は j - i で割り切れる。

制約

• 2 \le N \le 10^5
• 0 \le A_i \le 10^5

入力例 1

4
0 2 3 9

出力例 1

4

(1, 2), (1, 4), (2, 3), (3, 4) の 4 個です。

入力例 2

10
1 2 3 1 2 3 1 2 3 4

出力例 2

23

a_i - a_j が負であるような組も数えます。

問題文

えびまさんは (1,\ 2,\ ...,\ N) の順列 (P_1,\ P_2,\ ...,\ P_N) を持っていて、これを昇順に並び替えたいと考えています。

えびまさんは、以下の操作を好きな回数だけ行うことができます。 1 回も操作を行わないことも可能です。

• P_i と P_j をスワップする。この時、コスト |i-j| を支払う。

この時、えびまさんが順列を昇順に並び替えるまでに支払うコストが最小となる様な操作手順を求めてください。

制約

• 1 \leq N \leq 2000
• 1 \leq P_i \leq N
• i \neq j なら P_i \neq P_j

入力例 1

3
3 1 2

出力例 1

2
1 2
2 3

最初に 1 項目と 2 項目をスワップし、次に 2 項目と 3 項目をスワップすることでコストの総和が 2 となり、これが最小です。

入力例 2

10
3 7 10 1 9 5 4 8 6 2

出力例 2

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