[2017 ZROI Round #9]最小值

01-27

paste.ubuntu-ARZhus code of the Brute force algorithm

paste.ubuntu-ARZhus code with the stirling number

paste.ubuntu-std

好像這次又混到一個比較好的分數了（大霧。最後一題90分什麼鬼啊……

題意大抵就是對於一個數n，我們有n!個對於1~n的排列。對於每一個排列A_k，我們定義它的權值為：定義變數p=n+1，從下標為1的數開始向右掃，如果p>A_k[i]，那麼p=A_k[i]，權值就是p改變次數的平方。求n!個排列的權值之和。如果沒有理解，可以看下面的暴力程序。

其實在比賽的時候，第三題是沒有想出來的，於是寫了一個暴力程序，算出前11項：

int A[100];nint main() {ntrep(N,1,11) {nttrep(i,1,N) A[i]=i;nttint res=0,tmp,k;nttdo {nttttmp=0,k=N+1;ntttrep(i,1,N) if(k>A[i]) k=A[i],tmp++;ntttres=res+tmp*tmp;ntt} while(next_permutation(A+1,A+1+N)); nttprintf("%d ",res);nt}nntreturn 0;n}n

如果剛才沒有理解題意的，那麼這裡就應該很清楚了。得出的數就是如下的東西：

1 5 23 120 724 5012 39332 345832 3371976 36135792 422379792n

這時候，就應該打開The On-Line Encyclopedia of Integer Sequences? (OEIS?)，把這一坨數複製進去，然後就發現……http://oeis.org/search?q=1+5+23+120+724+5012+39332+345832+3371976+36135792+422379792&language=english&go=Search

好像……這個數列前人就總結過了？然後還有公式！公式：

$a(n)=(-1)^{n+1}cdot[s_s(n+1,2)-s_s(n+1,3)]$ 。

其中 $s_s(n,m)=begin{bmatrix} n m end{bmatrix}$ ，即有符號的斯特林一類數，代表n個元素構成m個圓排列的數目。雖然沒有研究過（flag:到時候研究），但是百度百科上給出了有符號斯特林一類數的遞推式： $s_s(n+1,m)=s_s(n,m-1)-ncdot s_s(n,m)$ .那麼就可以 $O(n)$ 遞推斯特林數了QwQ，然後就得出答案了。

但是，很明顯，我們不應該滿足於作弊(QAQ)，應該去想正解。在床上思考了一下，用遞推的思想分類討論，其實可以做出這一道題目。

我們考慮 n=i(i>0) 時，基於 i-1 遞推。那麼如果將 i 放在排列開頭，總共有 $(n-1)!$ 個排列，很明顯就會使每一個排列的未平方的權值 +1；不放在開頭，總共有 $(n-1)cdot (n-1)!$ 個排列，和之前的一模一樣。

這樣，我們可以很自然地想到奇妙遞推了。定義 $f_i=i!$ ， $s_i$ 為未平方權值和， $g_i$ 為答案。那麼遞推就比較自然了。

$f_i=f_{i-1}cdot i$ .

由於上述的分析，可以發現，除了 $s_{i-1}cdot i$ 這一根據排列數目翻了 i 倍這一特性之外，還要考慮對於 i 開頭的排列，又權值又增加了 $s_{i-1}$ ，那麼 $s_i=s_{i-1}cdot i+f_{i-1}$ .

平方和，如果 i 不放在開頭，那麼總權值就有 $(n-1)cdot g_{i-1}$ ;如果 i 放在開頭，那麼設 i-1 的每一個排列的未平方權值為 $a_k$ ，那麼 i 放在開頭時，權值和為

$sum_{k=1}^{(i-1)!}(a_k+1)^2=sum_{k=1}^{(i-1)!}(a_k^2+2a_k+1)=sum_{k=1}^{(i-1)^2}a_k^2+2sum_{k=1}^{(i-1)^2}a_k+(i-1)!=g_{i-1}+2s_{i-1}+f{i-1}$ 兩者相加，就可以得出遞推式： $g_i=g_{i-1}cdot i+2s_{i-1}+f_{i-1}$ .

同時， $f_0=1,s_0=0,g_0=0$ ，那麼直接遞推咯！

（這種題目放考場上其實有點慌啊）