#C240302A. A-棋子

网址（Website）

题目详情 - A-棋子 - Super

题解 - A-棋子 - Super

题解（Solution）

$\qquad$可以得到如果两个方块相对距离不变，对原答案不会有影响。（即从 _A_A_A_A_A_A_A 变为 A_A_A_A_A_A_A_ 不会有影响）
$\qquad$容易得出当两个方块挨在一起时后面的方块一定不能到前面去（如 _A_A_AAA__A_ ，这里最后的A一定不能直接跳到最前面去），对于这种情况，我们可以将方块按 A_A_A_A_... 排列，这样就保证了每遇到一个 A 就可以直接跳到前面去，如果这样摆之后还是有不能直接跳到的情况呢？（如将 _A_AAAA 变为 A_A_AAA后，最后的A还是不能直接跳到底）这个时候就只能在前面能跳的4个的 A 中选一个跳出去，有 $ans=ans\times4%mod$ 。

$\qquad$以此类推，我们就可以将所有的方案计算出来，最后剩下的所有数一定是可以直接跳的，每次选一个跳出去，有 $ans=ans\times(cnt!)$ ，其中 $cnt$ 为剩下的数的个数。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 101234;

vector<int> vec;
int n,ans=1;

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("a");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;int Tim = clock();
	vec.emplace_back(1);
	For(i,1,n){
		int x=input();if(i==1) continue;
		if(x==vec.back()+1){
			ans = ans*(vec.size()+1)%mod;
		}else vec.emplace_back(vec.back()+2);
	}int len = vec.size();
	For(i,1,len) ans = ans*i%mod;
	cout<<(ans%mod+mod)%mod<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}