Codeforces 1284C New Year and Permutation (R1700)

問題

整数 $n,\ m$ が与えられます。長さ $n$ の順列 $p$ のスコアを
$\max \{p_l, \ldots, p_r\}-\min\{p_l, \ldots, p_r\}=r-l$ を満たすような組 $(l,r)\ (1 \le l \le r \le n)$ の個数
とします。長さ $n$ の全ての順列のスコアの合計を $\bmod m$ で求めてください。

制約

$1 \le n \le 250000$
$10^{8} \le m \le 10^{9}$
$m$ は素数

考察

$\max \{p_l, \ldots, p_r\}-\min\{p_l, \ldots, p_r\}=r-l$ という条件について
部分列の長さを $len(=r-l+1)$ 、最小値を $m$ とおきます。この部分列が条件を満たすとすると、最大値は $m+len-1$ です。この部分列の長さを $len$ にするためにはあと $len-2$ 個の要素を追加しなければなりませんが、 $m$ より大きく $m+len-1$ より小さい要素が $len-2$ 個しか残っていないので、追加する数は一意に定まります。結局この条件は、 $p[l,r]$ が連続する整数からなる、という条件だと分かります。

全ての順列について部分列の個数を数える代わりに、各部分列が何回数えられるかを考えます。ある部分列が同じ順列に二度以上含まれることはないので、その部分列を含むような順列の個数が求めるものです。

まずは具体的な例で考えてみましょう。例えば $n=7$ のとき、 $a=(2, 3, 5, 4)$ を含む順列がいくつあるかを考えます。これは $a$ の位置が $4$ 通り、各場合について残りの要素の並べ方が $3!=6$ 通りあるので $4 \times 6=24通り$ あることが分かります。

これを全ての条件を満たす部分列について求めて足し合わせたものが答えです。この値は部分列の長さだけによるので、同じ長さの部分列をまとめて数えることができます。長さ $k$ の条件を満たす部分列は $(n-k+1) \times k!$ 通りあるので、結局答えは $\sum_{k=1}^{n} (n-k+1) \times k! \times (n-k+1) \times (n-k+1)!$ です。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int n,mod; cin>>n>>mod;
   vector<int> fact(n+1);
   fact[0]=1;
   for(int i=1;i<=n;i++) fact[i]=(Lint)i*fact[i-1]%mod;

   int ans=0;
   for(int k=1;k<=n;k++){
      ans+=(Lint)(n-k+1)*(n-k+1)%mod*fact[k]%mod*fact[n-k]%mod;
      ans%=mod;
   }
   cout<<ans<<endl;
   return 0;
}