MOD計算

code: Mod.js

class Mod {

constructor(mod) {

if (mod == null) { mod = Combinatorics.DefaultMod; }

this.mod = mod;

}

mult(a,b) {

let ret = 0;

a %= this.mod;

b %= this.mod;

while (b) {

if (b&1) {

ret += a;

if (ret > this.mod) { ret -= this.mod; }

}

a <<= 1;

if (a > this.mod) { a -= this.mod; }

b >>= 1;

}

return ret;

}

pow(a,b) {

let ret = 1;

while(b) {

if (b&1) { ret = this.mult(ret,a); }

a = this.mult(a,a);

b >>= 1;

}

return ret;

}

div(a,b) { return this.mult(a, this.pow(b, this.mod-2)) }

}

const MOD = new Mod(1e9+7);

参考

フェルマーの小定理による逆元より拡張ユークリッド互除法から算出する方が速い

参考

サンプル

code: arc071_d.js

solve() {

const nm = input.nextIntArr();

const x = input.nextIntArr();

const y = input.nextIntArr();

const dx = _.diffArray(x);

const dy = _.diffArray(y);

return MOD.mult(

_.modSum(dx.map((e,i)=> MOD.mult(MOD.mult((i+1),(dx.length - i)),e))),

_.modSum(dy.map((e,i)=> MOD.mult(MOD.mult((i+1),(dy.length - i)),e)))

);

}

_.modSum(dx.map((e,i)=> MOD.mult(MOD.mult((i+1),(dx.length - i)),e)))

を

dx.map((e,i)=> (i+1)*(dx.length-i)*e).sum()

ぐらいシンプルに書けたらいいのだけど...