yukicoder-271

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/271 No.271 next_permutation (2)] ==

=== Description ===

{{{
#!html
<p>对于$[1,2,\dots,n]$的一个置换$x$，定义$f(x)$是下一个字典序比$x$大的置换。如果$x=[n,n-1,\dots,1]$，那么$f(x)=[1,2,\dots,n]$。比如：$f([1,2,3])=[1,3,2]$, $f(f([3,1,2]))=f([3,2,1])=[1,2,3]$。</p>

<p>定义置换$x$的逆序对数为$\mathbf{inv}(x)$。比如：$\mathbf{inv}([2,1,3])=1$，$\mathbf{inv}([3,2,1])=3$。</p>

<p>给定一个置换$p$，定义如下置换序列$A$：$A_0=p$，$A_i=f(A_{i-1})$ ($i \in [1,2,\dots]$)。比如：$p=[2,1,3]$，$A=[[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$。</p>

<p>现在给出一个长度为$N$的置换$p$和一个整数$K$。求$\sum\limits_{i=0}^{K-1}\mathbf{inv}(A_i) \bmod (10^9+7)$。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$ $K$<br>
$p_1$ $p_2$ $\cdots$ $p_N$
</p>

<p>
第一行两个整数$N$ ($1 \le N \le 10^5$)和$K$ ($0 \le K \le 10^{18}$)。第二行一个$[1,2,\dots,N]$的排列$p$ ($1 \le p_i \le N$)。
</p>
}}}

=== Output ===

{{{
#!html
输出$\sum\limits_{i=0}^{K-1}\mathbf{inv}(A_i) \bmod (10^9+7)$。
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3 5
2 1 3
</pre>
}}}
输出
{{{
#!html
<pre>
8
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
3 36
1 2 3
</pre>
}}}
输出
{{{
#!html
<pre>
54
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
1 1000000000000000000
</pre>
}}}
输出
{{{
#!html
<pre>
0
</pre>
}}}

==== Sample 4 ====
输入
{{{
#!html
<pre>
2 1000000000000000000
1 2
</pre>
}}}
输出
{{{
#!html
<pre>
500000028
</pre>
}}}

No.271 next_permutation (2)

Description

对于$[1,2,\dots,n]$的一个置换$x$，定义$f(x)$是下一个字典序比$x$大的置换。如果$x=[n,n-1,\dots,1]$，那么$f(x)=[1,2,\dots,n]$。比如：$f([1,2,3])=[1,3,2]$, $f(f([3,1,2]))=f([3,2,1])=[1,2,3]$。

定义置换$x$的逆序对数为$\mathbf{inv}(x)$。比如：$\mathbf{inv}([2,1,3])=1$，$\mathbf{inv}([3,2,1])=3$。

给定一个置换$p$，定义如下置换序列$A$：$A_0=p$，$A_i=f(A_{i-1})$ ($i \in [1,2,\dots]$)。比如：$p=[2,1,3]$，$A=[[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$。

现在给出一个长度为$N$的置换$p$和一个整数$K$。求$\sum\limits_{i=0}^{K-1}\mathbf{inv}(A_i) \bmod (10^9+7)$。

Input

$N$ $K$
$p_1$ $p_2$ $\cdots$ $p_N$

第一行两个整数$N$ ($1 \le N \le 10^5$)和$K$ ($0 \le K \le 10^{18}$)。第二行一个$[1,2,\dots,N]$的排列$p$ ($1 \le p_i \le N$)。

Output

输出$\sum\limits_{i=0}^{K-1}\mathbf{inv}(A_i) \bmod (10^9+7)$。

Sample

Sample 1

输入

3 52 1 3

输出

Sample 2

输入

3 361 2 3

输出

Sample 3

输入

1 1000000000000000000

输出

Sample 4

输入

2 10000000000000000001 2

输出

500000028