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

1 則留言:

  1. If you're trying to lose weight then you certainly need to try this totally brand new custom keto plan.

    To produce this keto diet service, certified nutritionists, fitness couches, and professional chefs have united to develop keto meal plans that are productive, suitable, money-efficient, and delightful.

    Since their first launch in early 2019, hundreds of people have already transformed their body and health with the benefits a proper keto plan can provide.

    Speaking of benefits: clicking this link, you'll discover 8 scientifically-tested ones offered by the keto plan.

    回覆刪除