mod(ARC071D - 井井井 / ###)

atcoder.jp

電車の中で考察するとだいたい終わるし時間が潰せるので良い。

直線によって区切られている小さなマスについて、そのマスが長方形の中に含まれる回数は、縦横それぞれでその範囲が長方形に使われるかを
なのでまず一方の方向について考える。
実験してみたところ、その範囲が長方形の中として使われる回数は、その方向の「マスの個数」をnとするととなる。(直線の個数はn+1なので注意)

これを10^5マスについて計算しておき、それぞれのマスについて面積×(x方向の使う回数)×（y方向の使う回数）をしたいが、それは計算量が10^10なので間に合わない。
10^9+7は素数なので、であるので、横や縦について長さをかけた状態で一気にmodを取りながら足していき、最後にかけ算をしても答えは同じになる。

お恥ずかしながらよく使われるmodが素数であることに初めて気づいた。まあそうでなければ変な数字にしないよね。あとintを紛れ込ませることによってmodを取る前のかけ算した時点の答えがintで認識され、オーバーフローする場合に気をつける。それでWAを出した。

コード　計算量は

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long
 int main(){
     long long int n,m;
     scanf("%lld %lld",&n,&m);
     long long int x[100002],y[100002];
     long long int bx[100002],by[100002];
     rep(i,n){scanf("%lld",&x[i]);if(i>0)bx[i-1]=x[i]-x[i-1];}
     rep(i,m){scanf("%lld",&y[i]);if(i>0)by[i-1]=y[i]-y[i-1];}
     long long int mod=1000000007;
     long long int xans=0,yans=0;
     rep(i,n-1){
         long long int use=(n-1-i)*(i+1);
         xans+=(bx[i]*use)%mod;xans%=mod;
     }
     rep(i,m-1){
         long long int use=(m-1-i)*(i+1);
         yans+=(by[i]*use)%mod;yans%=mod;
     }
     printf("%lld\n",(xans*yans)%mod );
     
 }