## C - Bowls and Dishes

We have $N$ dishes numbered $1, 2, \dots, N$ and $M$ conditions numbered $1, 2, \dots, M$.

Condition $i$ is satisfied when both Dish $A_i$ and Dish $B_i$ have (one or more) balls on them.

There are $K$ people numbered $1, 2, \dots, K$. Person $i$ will put a ball on Dish $C_i$ or Dish $D_i$.
At most how many conditions will be satisfied?

Constraints

• All values in input are integers.
• $2 ≤ N ≤ 100$
• $1 ≤ M ≤ 100$
• $1 ≤ A_i < B_i ≤ N$
• $1 ≤ K ≤ 16$
• $1 ≤ C_i < D_i ≤ N$

Sample Input 1

Sample Output 1

## D - Staircase Sequences

How many arithmetic progressions consisting of integers with a common difference of $1$ have a sum of $N$?

Constraints

• $1≤N≤10^12$
• $N$ is an integer.

Sample Input 1

Sample Output 1

We have four such progressions:

• $[12]$
• $[3, 4, 5]$
• $[-2, -1, 0, 1, 2, 3, 4, 5]$
• $[-11, -10, -9, \dots, 10, 11, 12]$

## E - Magical Ornament

There are $N$ kinds of magical gems, numbered $1, 2, \ldots, N$, distributed in the AtCoder Kingdom.

Takahashi is trying to make an ornament by arranging gems in a row.

For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have $M$ pairs for which the two gems can be adjacent: (Gem $A_1$, Gem $B_1$), (Gem $A_2$, Gem $B_2$), $\ldots$, (Gem $A_M$, Gem $B_M$). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)

Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds $C_1, C_2, \dots, C_K$. If the answer is yes, find the minimum number of stones needed to form such a sequence.

Constraints

• All values in input are integers.
• $1 ≤ N ≤ 10^5$
• $0 ≤ M ≤ 10^5$
• $1 ≤ A_i < B_i ≤ N$
• If$i ≠ j, (A_i, B_i) ≠ (A_j, B_j)$.
• $1 ≤ K ≤ 17$
• $1 ≤ C_1 < C_2 < \dots < C_K ≤ N$

Sample Input 1

Sample Output 1

### 解法一

bfs+状态压缩，因为$K$很小，所以我们可以将给定的输入转换成一个双向图，然后将关键点之间的最短路径求出来，这里直接BFS就行了，时间复杂度$O(K*(N+M))$，得到一个$dist[i][j]$，表示第$i$-th关键点和第$j$-th个关键点的最短路径

• 入口：$dp[1 << i][i] = 1$，只选取一个关键宝石，序列长度为1
• 转移：$dp[mask|(1 << j)][j] = \min(dp[mask][i] + dist[i][j])$，枚举所有的选取状态，枚举所有以关键宝石作为结尾的状态，递推求最小值
• 出口：$\min_i(dp[(1 << k)-1][i])$，选取到所有的关键石头，并且以某个关键石头结尾的最小值

## F - Shift and Inversions

Given is a sequence $A = [a_0, a_1, a_2, \dots, a_{N-1}]$ that is a permutation of $0, 1, 2, \dots, N - 1$.

For each $k = 0, 1, 2, \dots, N - 1$, find the inversion number of the sequence $B = [b_0, b_1, b_2, \dots, b_{N-1}]$ defined as $b_i = a_{i+k \bmod N}$.

Constraints

• All values in input are integers.
• $2≤N≤3×10^5$
• $a_0,a_1,a_2,…,a_{N−1}$ is a permutation of $0,1,2,…,N−1$.

Sample Input 1

Sample Output 1

We have $A = [0, 1, 2, 3]$.

• For $k = 0$, the inversion number of $B = [0, 1, 2, 3]$ is $0$.
• For $k = 1$, the inversion number of $B = [1, 2, 3, 0]$ is $3$.
• For $k = 2$, the inversion number of $B = [2, 3, 0, 1]$ is $4$.
• For $k = 3$, the inversion number of $B = [3, 0, 1, 2]$ is $3$.