• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P2671 [NOIP2015 普及组] 求和

开发技术 开发技术 1周前 (07-19) 6次浏览

Archie

这是个什么东西呢

一看数据范围,肯定(o(n)),带个(log)都不太肯能,再一看体面,y似乎没大有用

移项,发现(x+y=2z)这是啥意思呢,就是说,x+y需要是偶数,x,y奇偶性相同,颜色相同,那么我们何不把这些东西扔到一块去

然后,每与每一对数推式子,发现对于有k个数的堆,他的贡献是(sum_{i=1}^k({i*number_i*(k-1)+i*(sum_{i-1}^knumber_i-number_i)}))

就可以(o(n))

记得多mod

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn=1e6+5;
int sum[maxn][2];
int num[maxn];
int col[maxn];
int cnt[maxn][2];
int ans;
const int mod=10007;
int n,m;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&num[i]);
		num[i]%=mod;
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&col[i]);
		sum[col[i]][i%2]+=num[i]%mod;
		sum[col[i]][i%2]%=mod;
		cnt[col[i]][i%2]+=1;
		cnt[col[i]][i%2]%=mod;
	}
	for(int i=1;i<=n;++i){
		if(cnt[col[i]][i%2]>1){
		ans+=(i%mod*num[i]%mod*((cnt[col[i]][i%2]-1)%mod)+i%mod*((sum[col[i]][i%2]-num[i])%mod)%mod)%mod;
		ans%=mod;
		}
	}
	cout<<ans%mod;
	return 0;
} 

程序员灯塔
转载请注明原文链接:P2671 [NOIP2015 普及组] 求和
喜欢 (0)