静かで孤独な日記

のんびりたまに

ARC071 D - 井井井 / ###

  • 問題

arc071.contest.atcoder.jp

  • エディトリアル

https://atcoder.jp/img/arc071/editorial.pdf

  • 感想

O(n+m)なのは想像がついた。
だけど、解けなかった。
xのトータルの長さとyのトータルの長さを掛けて答えが出ることも分かった。
だからあとはそのトータルの長さをO(n)とO(m)で求めるのだけど、その求め方が分からずエディトリアルを見た。
まぁ、簡単に書いてあって、そっかーって気持ちに。
なので、自分で考えて実装。
トータルの求め方は少しエディトリアルと違ってるが本質的には同じ。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

int n,m;
int x[100001],y[100001];
const ll MOD=(ll)1e9+7;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
    freopen("out","w",stdout);
#endif
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  for(int i=0;i<m;i++){
    cin>>y[i];
  }
  ll xsum=0,ysum=0;
  ll now=n-1;//x[n-1]に付く係数
  for(int i=n-1;i>=0;i--){
    xsum+=now*x[i];
    now-=2;//xに付く係数は毎回-2すれば良い
  }
  now=m-1;//xの時と同じ
  for(int i=m-1;i>=0;i--){
    ysum+=now*y[i];
    now-=2;
  }
  cout<<((xsum%MOD)*(ysum%MOD))%MOD<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}