首页 > 其他分享 >AtCoder Beginner Contest 378 E

AtCoder Beginner Contest 378 E

时间:2024-11-05 21:22:22浏览次数:4  
标签:AtCoder Beginner int res ll update 378 abc378 define

https://atcoder.jp/contests/abc378/tasks/abc378_e
https://atcoder.jp/contests/abc378/editorial/11300

#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x)&-(x)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+10,mod=1e9+7;
ll n,m,k;
ll tree[N],a[N],s[N];
void update(int p){
    p++;
    while(p<=m){
        tree[p]++;
        p+=lowbit(p);
    }
}
ll query(int p){
    ll res=0;
    p++;
    while(p){
        res+=tree[p];
        p-=lowbit(p);
    }
    return res;
}
void solve(){
    cin>>n>>m;
    ll sum=0,res=0;
    //update(0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=(s[i-1]+a[i])%m;
        res+=s[i]*i-sum;
        sum+=s[i];
        res+=m*(i-1-query(s[i]));
        update(s[i]);
    }
    cout<<res<<endl;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int _=1;
    //cin>>_;
    while(_--) solve();

    return 0;
}

标签:AtCoder,Beginner,int,res,ll,update,378,abc378,define
From: https://www.cnblogs.com/djhjojo/p/18528874

相关文章

  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 洛谷题单指南-二叉堆与树状数组-P3378 【模板】堆
    原题链接:https://www.luogu.com.cn/problem/P3378题意解读:实现二叉堆。解题思路:二叉堆本质上一棵完全二叉树,根节点称为堆顶,根据特性不同分为有两种:大根堆:所有父节点的值大于子节点,根节点最大小根堆:所有父节点的值小于子节点,根节点最小主要作用:动态维护序列,并快速找到最大/最......
  • AtCoder Beginner Contest 378
    AtCoderBeginnerContest378总结A直接模拟,存\(1\)到\(4\)出现个数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<map&g......
  • AtCoder Beginner Contest 378
    ABC378光速切掉前四题,结果倒在了第五题。A-Pairing难度:红。弱智题,不解释。#include<bits/stdc++.h>usingnamespacestd;intmain(){inta[5]={0};for(inti=1;i<=4;i++){intx;cin>>x;a[x]++;}intans=0;for(inti=1;i<=4;i++){......
  • AtCoder
    AtCoder做题记录AtCoderBeginnerContest378APairing检查一下\(1\sim4\)各有几个即可。代码BGarbageCollection根据\(d\)求出当天的余数,让后和\(r\)比较一些即可。代码。CRepeating用map存上一个该数的位置。代码。DCountSimplePaths疑似深搜板子。代......
  • AtCoder Beginner Contest 378 F题题解
    题目:F-AddOneEdge2思路:可以发现题目就是要我们找出有多少个点对满足连成后是一个简单环环上的点度都为3因为是一个简单图所以不可以有重边和自环那么就代表着这个环肯定是由两个度为2的点和大于1个度为3的点组成的注意到两个点的最近公共祖先一定可以跟这两个点形......
  • AtCoder Beginner Contest 378
    省流版A.判断奇偶性即可B.根据余数计算偏移天数即可C.用map记录每个数出现的位置即可D.枚举起点,枚举每步的方向,朴素搜索即可E.考虑前缀和的两数相减代替区间和的情况,减为负数则加回正数,用树状数组维护减为负数的情况数F.枚举点,作为连边的俩个点的lca,考虑维护路径点......
  • ABC378
    A-Pairing简单模拟。B-GarbageCollection找到一个大于等于\(d\)的最小值,满足模$q=r$。简单分讨。C-Repeating简单模拟。D-CountSimplePaths纯DFS。枚举每个起点,暴力搜索统计答案。E-ModSigmaProblemF-AddOneEdge2G-Everlas......