問題一覧 > 通常問題

No.270 next_permutation (1)

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : anta
お気に入りにしたユーザー ProblemId : 569 / 自分の提出
問題文最終更新日: 2026-06-25 03:30:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 118 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。