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