はじめに

AtCoder：競技プログラミングコンテストを開催する国内最大のサイトをはじめとする競技プログラミングでは、「割ったあまり」を求める問題が頻繁に出題されます。
そこで、Perl 用のテンプレートを準備します。

剰余の基本

割る整数を法といいますが、ここでは 1,000,000,007 を法として説明いたします。
変数の初期化は、お好きな方法で。

mod.pl

$mod1 = 1000000007;
$mod2 = 1_000_000_007;
$mod3 = 1e9 + 7;

print $mod1, "\n"; # => 1000000007
print $mod2, "\n"; # => 1000000007
print $mod3, "\n"; # => 1000000007

足し算

add.pl

$a += $mod + $b;
$a %= $mod;

変数が負のケースに対応するよう法を足しておきます。

引き算

sub.pl

$a += $mod - $b;
$a %= $mod;

マイナスにならない様、法を足しておきます。

掛け算

mul.pl

$a *= $b;
$a %= $mod;

割り算

割り算だけ別の計算が必要になります。

割り算の剰余：逆元

割り算の場合、法($mod)で直接割って求めることはできないので、法から逆元を求め、逆元を掛けることにより割り算の代用とします。

modinv.pl

sub modpow {
  my ($a, $n, $mod) = @_;
  my $res = 1;
  while ($n > 0) {
    $res = $res * $a % $mod if $n & 1;
    $a = $a * $a % $mod;
    $n >>= 1;
  }
  return $res;
}
sub modinv {
  my ($a, $mod) = @_;
  return modpow ($a, $mod - 2, $mod);
}
sub main {
  for (my $i=1; $i<13; $i++) {
    print "$i 's inv: " . modinv ($i, 13) . "\n";
  }
  my $a = 12345678900000;
  my $b = 100000;
  my $mod = 1_000_000_007;
  $a %= $mod;
  print $a * modinv ($b, $mod) % $mod, "\n"; # => 123456789
}
main();

\$a に \$b と \$mod から求めた逆元を掛けて、$mod で余りを求めます。

print.pl

  print $a * modinv ($b, $mod) % $mod, "\n"; # => 123456789

ABC 156 D

AtCoder Beginner Contest 156 D - Bouquet

ABC156D.pl

use strict;
use warnings;

my ($n, $a, $b);
{
  my $in = <STDIN>;
  ($n, $a, $b) = split(" ", $in);
}
my $MOD = 1e9 + 7;
my $modpow = sub {
  my ($a, $n, $MOD) = @_;
  my $res = 1;
  while ($n > 0) {
    $res = $res * $a % $MOD if $n & 1;
    $a = $a * $a % $MOD;
    $n >>= 1;
  }
  return $res;
};
my $modinv = sub {
  my ($a, $MOD) = @_;
  return $modpow->($a, $MOD - 2, $MOD);
};
my $comb = sub {
  my ($n, $k) = @_;
  my $a = 1;
  my $b = 1;
  for (my $i=0; $i<$k; $i++) {
    $a *= $n - $i;
    $a %= $MOD;
    $b *= $i + 1;
    $b %= $MOD;
  }
  $a * $modinv->($b, $MOD) % $MOD;
};

my $ans = $modpow->(2, $n, $MOD) - 1;
$ans += $MOD - $comb->($n, $a, $MOD);
$ans += $MOD - $comb->($n, $b, $MOD);
print $ans % $MOD, "\n";

うーん、$MODだらけ

java の場合

javaの場合、java.math.BigInteger がライブラリとして準備されており、

modInverse(BigInteger m)：逆元
modPow(BigInteger exponent, BigInteger m)：べき乗
gcd(BigInteger val)：最大公約数

などがメソッドとして利用可能です。

まとめ

本番で実装するには時間が短すぎる
習うより慣れよ

参照したサイト
「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜
クラスBigInteger
本日の精進：逆元と組み合わせ問題

追記

Perl で学ぶ逆元の２ + パナソニックプログラミングコンテスト2020 C で嵌った話 にて、AtCoder Beginner Contest 156 D - Bouquet の別解法を投稿しました。

追記２

足し算でも変数が負の場合、正しく計算されるように変更しました。
Perl で学ぶ逆元の３ ABC 151 E が解けた！

Perl で学ぶ剰余計算

はじめに

剰余の基本

割り算の剰余：逆元

ABC 156 D

java の場合

まとめ

追記

追記２