1 条题解
-
1
//数学归纳 //首先要分奇偶,和不同颜色 //分类后求出每一项的id,num,id*num的和 //推导:对于某一类的项目 //其分数为(id1+id2)(num1+num2)+(id1+id3)(num1+num3)+..+(idn-1 + idn)(numn-1 +numn) //把其中的id1相关的拆出来为id1*(num1+num2 + num1+num3 +..+ num1+numn) //化简为id1(num1+num2+...+numn)+(n-2)id1*num1 //由此可以得出,总得分为 //(id1+id2+...+idn)(num1+num2+...+numn)+(n-2)(id1*num1+id2*num2+...+idn*numn) //注意乘了会爆int #include<bits/stdc++.h> using namespace std; int n,m; long long a[100005],c[100005]; long long id[2][100005]; //分别计算奇/偶项,颜色为j的 id,num,id*num的和 long long num[2][100005]; long long idnum[2][100005]; long long cnt[2][100005]; //统计有多少项 int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>c[i]; for(int i=1;i<=n;i++) { id[i%2][c[i]] +=i; id[i%2][c[i]]%=10007; num[i%2][c[i]] +=a[i]; num[i%2][c[i]]%=10007; idnum[i%2][c[i]] +=i*a[i]; idnum[i%2][c[i]]%=10007;//i*a[i]会爆int cnt[i%2][c[i]]++; } long long ans=0; for(int i=0;i<=1;i++) { for(int j=1;j<=m;j++) { if(cnt[i][j]<2)continue;//只有大于2才有,否则算了就出错了 ans+=id[i][j] * num[i][j] ; ans%=10007; ans+=(cnt[i][j]-2)*idnum[i][j]; ans%=10007; } } cout<<ans; return 0; }
- 1
信息
- ID
- 646
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 26
- 已通过
- 3
- 上传者