2015年8月8日 星期六

[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) ;
}
 

沒有留言:

張貼留言