制約からして二分探索なんだろうとは思ったが本番では解けなかった。 a,bを最初にソートしておき、付値関数C(x)として次のものを考える。C(x): a[i]*b[j]a[i]*b[pos]x のとき、a[i]x なるpos'について pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。 …

をmod 1e9+7 での逆元を使いながら計算すれば良い。最初 #define MOD 1000000007 としていたが、これだとMODはint型と判断されオーバーフローを起こしてしまってつらかった。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) </bits/stdc++.h>…