欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数论】洛谷P2671 求和

程序员文章站 2022-07-16 10:51:56
...

题目

【数论】洛谷P2671 求和
【数论】洛谷P2671 求和

Sample-1 in
6 2
5 5 3 2 2 2
2 2 1 1 2 1
Sample-1 out
82
Sample-2 in
15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1
Sample-2 out
1388

1. 分析题目发现
  • 三元组分数与y无关
  • x,z同色
  • x,z的位置i 必定同为双数或者同为单数
2. 然后

我们就可以把同色,同单双的数分到一类计算分数。

3. 再

简化计算公式,用前缀和优化一下即可。
具体如下:
【数论】洛谷P2671 求和
对于某组第一个点来说,需要乘上它的编号的有 t-1组(它本身的num+其他点的num)(如上图的式子,用一个sum在读入的时候就加上所有数的num,这里已经有一个第一个点的num。剩下需要加的就是t-2个num。
【数论】洛谷P2671 求和


Code

#include<cstdio>
#define ll long long
#define mod 10007
ll n,m,ans,num[1000001],color[1000001],t[1000001][5],sum[1000001][5];
int main(){
   scanf("%lld%lld", &n, &m);
   for(ll i = 1; i <= n; ++i)
     scanf("%lld", &num[i]);
   for(ll i = 1; i <= n; ++i){
      scanf("%lld",&color[i]);
      ++t[color[i]][i % 2];  //同类数量
      sum[color[i]][i % 2] = (sum[color[i]][i % 2] + num[i]) % mod;
      //同类的数字和
   }
   for(ll i = 1; i <= n; ++i)
     ans = (ans + i * ((t[color[i]][i%2]-2) * num[i] + sum[color[i]][i%2]) % mod) % mod;
   //如上
   printf("%lld", ans);
}
相关标签: 数论