2016年1月14日 星期四

[HOJ 284][ABBYY Cup 3.0]PE Lesson

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

這題CBD的題解寫得不錯,不過從他的轉移公式要推出一般式可能會需要一些數學技巧QAQ
在這裡我用另一個簡單許多的角度解釋轉移公式(我承認是看了他的題解才會這題XD)
首先,我們先照著CBD的思路
對於一個排列,要怎麼判斷他是否可以在有限的交換次數內換回來呢?
我們知道,一個排列可以拆成很多圈,因此只要把這些圈分開研究就可以了
首先我們可以證明:
只要一個大小為n的集合裡面「只能換一次的人數」不超過2,就可以形成一個圈

先證明2人的情況可以形成一個圈:
假設要經過x0 -> x1 ->...-> x_i -> a -> x_(i+2) ->...-> x_j -> b -> x_(j+2) ->...-> x0的輪迴才能把序列變回來,其中a和b是只能交換一次的人
首先,先讓a和b得到他想要的東西,也就是進行交換(a,x_(i+2))和(b,x_(j+2))
然後i+2和i+3這兩個位置再互換...以此類推,b後面也是一樣
最後,剩下i和j這兩個位置還沒得到想要的東西(i(想要a)存的是b,j(想要b)存的是a)
這時,i和j再進行一次交換就好了

再來證明3人的情況無法形成一個圈:
要換回來,至少要交換n-1次,但是這群人能交換的最多次數是(3*1+(n-3)*2)/2向下取整=n-2次,所以是不可能換回來的

證明完畢---*
\
先跟大家講一下,上面那些證明不是重點www(遭踢飛
所以,我們可以先把只能換一次的人(以下稱X)依照位置編號,假設是1~A好了,可以換兩次的(以下稱Y)也依照位置編號為A+1~N吧
我們可以先決定1~A各要分配在那些圈裡面(同一個圈最多兩人),假設有c(A)種合法的分配
取其中一種分配方式
這時再把A+1~N插進入(順序和插入位置都是隨便的),我們對於每個X
1. 如果他沒有和另一個配對,就和排在他之後直到碰到另一個X之間的所有Y照排隊順序形成一個置換
2. 如果他和X2配對,那就把X2之後的Y也含進這個圈裡面,變成X、Y1、Y2...Yi、X2、Yi+1...
可以發現,以上分配法剛好跟每一種合法置換方式一一對應
而對於X的每一種分配方式,把Y插入之後可能產生的情況就有N!/A!種(先X和Y全部一起亂排,再把X排好),所以答案就是c(A)*N!/A!了!

再來講c(A)怎麼算

A=1時,c(A)=1
A=2時,c(A)=2
A=n時,第A個人有兩種分配方式
1. 自己的圈沒有其他人:c(A-1)
2. 從其他A-1個人選一個和自己住同一個圈:(A-1)*c(A-2)
因此,遞迴式就出來了:c(A)=c(A-1)+(A-1)*c(A-2)
可以用記憶化搜索實作,複雜度為O(N)

code:
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
int N;
vector<LL>DP;
LL GetDP(const int i)
{
 if(i<(int)DP.size())return DP[i];
 DP.push_back(((i-1)*GetDP(i-2)+GetDP(i-1))%MOD);
 return DP[i];
}
int main()
{
 if(true)
 {
  int *t=new int[3]{1,1,2};
  for(int i=0;i<3;i++)DP.push_back(t[i]);
  delete[]t;
 }
// freopen("in.txt","r",stdin);
 while(scanf("%d",&N)==1)
 {
  LL a=0LL,b=0LL;
  for(int i=0,v;i<N;i++)scanf("%d",&v),(v==1?a:b)++;
  LL ans=GetDP(a);
  for(LL i=a+1LL;i<=a+b;i++)(ans*=i)%=MOD;
  printf("%lld\n",ans);
  break;
 }
 return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原