No.270 next_permutation (1)
タグ : / 解いたユーザー数 43
作問者 :
anta
Problem Statement
For a permutation $x$ of $[1,2,\ldots,n]$ for some $n$, let $f(x)$ be the permutation that comes right after $x$ in lexicographic order. However, if $x$ is the lexicographically last permutation $[n,n-1, \ldots, 1]$, then $f(x)$ is defined as the lexicographically first permutation $[1,2,\ldots,n]$. For example, $f([1, 2, 3]) = [1, 3, 2]$, $f(f([3,1,2])) = f([3,2,1]) = [1,2,3]$.
For two arrays $x, y$ of length $n$ for some $n$, the $L_1$ distance $\displaystyle \sum_{i=1}^n |x_i - y_i|$ is denoted by ${\rm dist}(x, y)$. For example, if $x = [1,2,3], y = [3,2,1]$, then ${\rm dist}(x, y) = |1-3| + |2-2| + |3-1| = 4$.
Given a permutation $p$, define a sequence of permutations $A$ by $A_0 = p$, $A_i = f(A_{i-1})$ ($i \in [1,2,\ldots]$). That is, $A_i$ is the result of applying $f$ to $p$ $i$ times. For example, if $p = [2,1,3]$, then $A = [[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$. Note that the indices of $A$ start from 0.
You are given an integer $N$, an integer $K$, a permutation $p$ of length $N$, and an array $B$ of length $N$ as input. Find $\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$.
Input
$N$ $K$ $p_1$ $p_2$ $\ldots$ $p_N$ $B_1$ $B_2$ $\ldots$ $B_N$
The first line contains integers $N (1 \le N \le 10^5)$ and $K (0 \le K \le 10^5)$, separated by a space. The second line contains a permutation $p$ of $[1,2,\ldots,N]$ of length $N$, separated by spaces. The third line contains an integer array $B (1 \le B_i \le 10^8)$ of length $N$, separated by spaces.
Output
Output $\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$ on one line.
Hint
The fact that the quantity being summed is the $L_1$ distance is not of great significance.
Sample
Sample 1
Input
3 5 2 1 3 3 2 1
Output
12
This is the example of $A$ given in the problem statement. The values of ${\rm dist}$ are $[4, 2, 2, 0, 4]$, so the answer is their sum, $12$.
Sample 2
Input
3 36 1 2 3 1 1 1
Output
108
In this case, $A$ cycles with period $3! = 6$. The sum of ${\rm dist}$ over one period is $18$, so the answer is $18 \times \frac{36}{6} = 108$.
Sample 3
Input
1 100000 1 1
Output
0
Sample 4
Input
2 100000 1 2 100000000 100000000
Output
19999999700000
Be careful of overflow.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。