记录编号	335537	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015PJ]求和	最终得分	100
用户昵称	千世断魂自凝眉	是否通过	通过
代码语言	C++	运行时间	0.560 s
提交时间	2016-11-02 14:38:43	内存使用	5.63 MiB

#include<cstdio>
#include<cstring>
#define mod 10007
#define LL long long
using namespace std;
const int maxn=100005;
LL n,m;
LL ans=0;
LL num[maxn],col[maxn],head[maxn],Last[maxn]={0},Next[maxn],odd[maxn],even[maxn],Odd,Even;

void Init(){
	if(odd[0]>1){
		for(int i=1;i<=odd[0];i++)
			ans=(ans+(num[odd[i]]*(((odd[0]-2)*odd[i]%mod)%mod+Odd))%mod)%mod;
	}
	if(even[0]>1){
		for(int i=1;i<=even[0];i++)
			ans=(ans+(num[even[i]]*(((even[0]-2)*even[i]%mod)%mod+Even))%mod)%mod;
	}
}

int main()
{
	freopen("2015sum.in","r",stdin);
	freopen("2015sum.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
	for(int i=1;i<=n;i++){
		scanf("%lld",&col[i]);
		if(!Last[col[i]]) head[col[i]]=i;
		if(Last[col[i]]) Next[Last[col[i]]]=i;	
		Last[col[i]]=i;
	}
	for(int i=1;i<=m;i++){
		int t=head[i];
		odd[0]=even[0]=0;
		Odd=Even=0;
		while(t){
			if(t&1){Odd+=t;odd[++odd[0]]=t;}
			else{Even+=t;even[++even[0]]=t;}
			t=Next[t];
		}
		Init();
	}
	printf("%lld\n",ans%mod);
	return 0;
}