题解 CF316D3 【PE Lesson】

· · 题解

小清新思维题

题解：

首先很容易发现答案与顺序无关，只与"1","2"的数量有关，并记"1"的个数为a，"2"的个数为b

首先考虑b=0的情况

设f[i]表示剩余i个"1"时的排列数

很容易得到转移f[i]=f[i-2]\times (i-1)+f[i-1]，表示(i-1)种方法选1个互换，1种方法选自己保持不变

考虑扩展到b\ne 0的情况

我们把2次交换的限制看成一次主动交换和一次被动交换

那我们就可以让b个"2"都先使用一次主动交换

那么第一个"2"可以从n个中选一个

第二个"2"可以从n-1中选一个

第三个"2"可以从n-2中选一个

。。。以此类推

这样b次交换后会剩下正好a个"1"（可以用数学轻松证明）

于是答案ans=f[a]\times \prod\limits_{i=1}^{b}(n-i+1)

代码：

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=1e9+7,N=1e6+5;
int n,ans=1,cnt,f[N];

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++){
        read(x);
        if(x==1) cnt++;
    }
    f[0]=f[1]=1;
    for(int i=2;i<=cnt;i++) f[i]=(f[i-2]*(i-1)+f[i-1])%mod;
    for(int i=n;i>cnt;i--) ans=ans*i%mod;
    write(ans*f[cnt]%mod);
}