记录编号	206289	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的验证码	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2015-11-06 15:43:10	内存使用	1.49 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZEN=100010;
int N;
int A[SIZEN]={0};
vector<int> pos1,pos2;
LL F1[SIZEN],F2[SIZEN];//F1是前缀有几个1,F2是后缀有几个2
LL G[SIZEN]={0};//有多少个"1..2",2的后端<=i
LL calc(const vector<int> &p1,const vector<int> &p2){//计算"1..2..1..2"的数量
	memset(F1,0,sizeof(F1));
	memset(F2,0,sizeof(F2));
	for(int i=0;i<p1.size();i++) F1[p1[i]]=1;
	for(int i=0;i<p2.size();i++) F2[p2[i]]=1;
	for(int i=2;i<=N;i++) F1[i]+=F1[i-1];
	for(int i=N-1;i>=1;i--) F2[i]+=F2[i+1];
	memset(G,0,sizeof(G));
	for(int i=0;i<p2.size();i++) G[p2[i]]=F1[p2[i]];
	for(int i=2;i<=N;i++) G[i]+=G[i-1],G[i]%=MOD;
	//我们枚举第二个"1"
	LL ans=0;
	for(int i=0;i<p1.size();i++){
		LL now=G[p1[i]-1]*F2[p1[i]+1]%MOD;
		ans=(ans+now)%MOD;
	}
	return ans;
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&A[i]);
		if(A[i]==1) pos1.push_back(i);
		else pos2.push_back(i);
	}
}
int main(){
	freopen("asm_code.in","r",stdin);
	freopen("asm_code.out","w",stdout);
	read();
	LL ans=(calc(pos1,pos2)+calc(pos2,pos1))%MOD;
	cout<<ans<<endl;
	return 0;
}