题解 CF316D3 【PE Lesson】
yuzhechuan · · 题解
小清新思维题
题解:
首先很容易发现答案与顺序无关,只与"1","2"的数量有关,并记"1"的个数为
首先考虑
设
很容易得到转移
考虑扩展到
我们把2次交换的限制看成一次主动交换和一次被动交换
那我们就可以让
那么第一个"2"可以从
第二个"2"可以从
第三个"2"可以从
。。。以此类推
这样
于是答案
代码:
#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);
}