[HOJ 284] PE Lesson

作法：

我們先觀察：對於一個排列，要怎麼判斷他是否可以在有限的交換次數內換回來。我們知道一個排列可以拆成很多圈，因此只要把這些圈分開研究就可以了。首先我們可以證明：對於每個圈，他能夠換完並且滿足限制的充要條件為：圈上的只能換一次的人數$\leq 2$。從右推到左不難，只要構造出一種換法就可以了。至於從左推到右，首先我們可以數歸出：對於一個大小為$k$的圈，至少要換$k-1$次才能把所有數歸位。而當作一次交換動作時，相應的兩個人的限制值都會減$1$，也就推得了所有人的限制值總和必須$\geq 2k-2$，所以至多有兩個人只能換$1$次。

另外再注意到，其實重要的只有有多少人能換一次，和有多少人能換兩次而已。因為我們可以任意交換兩人的 index 和限制值而不影響答案。因此現在問題變成：給定$x,y$（代表輸入中有$x$個$1$和$y$個$2$），找出滿足以下條件的$1,...,x+y$的排列個數：排列中的每個圈至多有兩個$1,..,x$之中的數。而這可以先想到一個DP的作法，也就是令$dp[x][y]$為所求的答案，那麼有邊界$dp[x][y]=(x+y)!$當$x\leq 2$。再來看要怎麼求$dp[x][y]$，考慮$x$這個數所在的圈，分成兩種可能：這個圈有$1$個或$2$個$1,...,x$之中的數。枚舉這個圈中用到了幾個$x+1,...,x+y$之間的數就可以得到轉移式：
$\displaystyle dp[x][y]=\sum_{i=0}^{y}dp[x-1][y-i]\frac{y!}{(y-i)!}+$$\displaystyle (x-1)\sum_{i=0}^{y}dp[x-2][y-i]\frac{y!}{(y-i)!}\cdot (i+1)$

可以先寫個程式算出這個DP表格，觀察前幾項可以發現：$\displaystyle dp[x][y]=dp[x][0]\cdot \frac{(x+y)!}{x!}$，所以只要遞推出$dp[x][0]$再計算答案就可以了。至於上面這條的證明就只要直接代入轉移式數歸，然後把組合級數化簡就可以了，詳細過程在這裡省略。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=1000000+10 ;
LL a[maxn] ;
main()
{
    int n,x=0,y=0 ; char k ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        k=getchar() ;
        while(k!='1' && k!='2') k=getchar() ;
        (k=='1'?x:y)++ ;
    }
    a[0]=a[1]=1 ;
    for(int i=2;i<=x;i++) a[i]=(a[i-1]+(i-1)*a[i-2])%MOD ;
    LL ans=a[x] ;
    for(int i=x+1;i<=n;i++) ans=ans*i%MOD ;
    printf("%lld\n",ans) ;
}