Perl で学ぶ逆元の３ ABC 151 E が解けた！

はじめに

逆元問題が好きになってきたので、調子に乗って E - Max-Min Sums に挑戦したが、難易度水色だったため簡単に解けるはずもなく気持ちが Light Blue になりながらも、何とか乗り切った話。

E - Max-Min Sums

AtCoder Beginner Contest 151 E - Max-Min Sums
答えは非常に大きくなる可能性があるので、

mod\ 10^9 +7

で出力してください。
この時点で、テンションは Max だった。

嵌ったところ

before1.pl

  $ans += $a[$n-$i-1] * $c;
  $ans %= $MOD;
  $ans += ($MOD - $a[$i]) * $c;
  $ans %= $MOD;

足し算なのでそのまま加えていましたが、加える変数 $a が負の場合、WA となるケースが考えられます。

after1.pl

  $ans += ($MOD + $a[$n-$i-1]) * $c; # 負にならない様、法を加算
  $ans %= $MOD;
  $ans += ($MOD - $a[$i]) * $c;
  $ans %= $MOD;

before2.pl

use Math::BigInt; # perl の bigint は圧倒的に遅い

my $modinv = sub {
  my $a = shift;
  Math::BigInt->new($a)->bmodinv($MOD); # BigInt メソッド
};

この投稿 で、Math::BigInt の味を占めたので使用しましたが、perl の bigint は圧倒的に遅い に気付かず TLE の山。

after2.pl

my $modinv = sub {
  my $a = shift;
  $modpow->($a, $MOD - 2); # 自作関数
};

解けたところ

ABC151E.pl

use v5.18; # strict say state
use warnings;

my ($n, $k) = split / /, <STDIN>;
my @a = split / /, <STDIN>;
@a = sort { $a <=> $b } @a;
my $MOD = 1e9 + 7;
my $modpow = sub {
  my ($a, $n) = @_;
  my $r = 1;
  while ($n > 0) {
    $r = $r * $a % $ MOD if $n & 1;
    $a = $a * $a % $MOD;
    $n >>= 1;
  }
  return $r;
};
my $modinv = sub {
  my $a = shift;
  $modpow->($a, $MOD - 2);
};
my (@fac, @finv);
$fac[0] = 1;
$finv[0] = 1;
for my $i (1..$n) {
  $fac[$i] = $fac[$i-1] * $i % $MOD;
  $finv[$i] = $modinv->($fac[$i]);
}
my $combi = sub {
  my ($n, $k) = @_;
  $fac[$n] * ($finv[$n-$k] * $finv[$k] % $MOD) % $MOD;
};
my $ans = 0;
for (my $i=0; $i<=$n-$k; $i++) {
  my $c = $combi->($n-$i-1, $k-1);
  $ans += ($MOD + $a[$n-$i-1]) * $c;
  $ans %= $MOD;
  $ans += ($MOD - $a[$i]) * $c;
  $ans %= $MOD;
}
say $ans;

AC
どやっ

まとめ

• 水色は骨のあるやつだった

参照したサイト

• 多倍長整数演算の速度比較
• Perl で学ぶ逆元の２ + パナソニックプログラミングコンテスト2020 C で嵌った話
• Perl で学ぶ剰余計算

追記

BigInt を使用すると100倍遅いことが分かりました
Perl AtCoderでベンチマーク