AC Libraryはmodintという構造体があり、これを使うと自動でmodを取ってくれます。aをb乗したものをmodで割った余りを計算するときは自分で実装しなくても繰り返し二乗法で高速な計算をしたり、割り算をするときも逆元を求めて計算結果を返してくれたりします。C# にはこのような便利なものはないのでしょうか？
ac-library-csharp にはこれに近い処理をする構造体が定義されています。StaticModInt や DynamicModInt がそれです。
Contents
Mod が固定値のときは StaticModInt構造体
a の b 乗 を 1000000007 で割った余りはこれで取得できます。
|
1 2 3 |
StaticModInt<Mod1000000007> res = 2; res = res.Pow(10); Console.WriteLine(res.Value); // 2 の 10 乗 を 1000000007 で割った余り 1024 |
% 演算子をつかって引き算をするときは a % b < 0 になるときは注意が必要なのですが、StaticModInt構造体であれば自動でうまくやってくれます。
|
1 2 |
StaticModInt<Mod1000000007> res = -10; Console.WriteLine(res.Value); // 負数ではなく 0 以上の整数（この場合は 999999997）が返される |
逆元も Inv メソッドで簡単に取得できます。
|
1 2 |
StaticModInt<Mod1000000007> res = 10; Console.WriteLine(res.Inv()); // 700000005 |
mod の割り算は逆元を掛け算するのですが、これも普通に割り算と同じような記述をすることでやってくれます。
|
1 2 3 4 |
StaticModInt<Mod1000000007> res = 2; StaticModInt<Mod1000000007> div = 10; Console.WriteLine(res / div); // 400000003 Console.WriteLine(res * div.Inv()); // 400000003 両者は当然一致する |
D – Knight を解く
問題を解いてみます
問題の概要
二次元グリッドの原点 (0, 0) にチェスのナイトの駒がある。
ナイトの駒はマス (i, j) にあるとき (i + 1, j + 2) か (i + 2, j + 1) のどちらかのマスにのみ動かすことができる。
ナイトの駒をマス (X, Y) まで移動させる方法は何通りあるか 10^9 + 7 で割った余りを求めよ。
(i + 1, j + 2) に動かす回数を N、 (i + 2, j + 1) に動かす回数を M とすると
N + 2 * M = X
2 * N + M = Y
という連立方程式が得られます。これを解くと
N = (2 * Y – X) / 3;
M = (2 * X – Y) / 3;
となります。答えは C(N + M, N) 通りとなります。
考え方として ◯ が N 個、● が M 個 あり、N 個並んでいる ◯ の間（間だけでなく先頭と最後尾も含む）に ● を挿入する（同じ場所に複数挿入するのもありとする）方法は何通りあるかを考えます。すると重複組合せ H(N + 1, M) となります。
また重複組合せの公式より H(n, k) = C(n + k – 1, k) なので求めるべき解は C(N + M, N) となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using AtCoder; class Program { // 二項係数を求める public static int BinoMod(int N, int K) { StaticModInt<Mod1000000007> res = 1; for (long n = 0; n < K; ++n) { res *= N - n; res /= n + 1; } return res.Value; } static void Main() { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int X = xy[0]; int Y = xy[1]; int mod = (int)Math.Pow(10, 9) + 7; int N = (2 * Y - X) / 3; int M = (2 * X - Y) / 3; // 連立方程式が非負整数解を持たない場合は 0 if ((2 * Y - X) % 3 != 0 || (2 * X - Y) % 3 != 0 || N < 0 || M < 0) Console.WriteLine(0); else Console.WriteLine(BinoMod(N + M, N)); } } |
Mod が固定値ではない場合 DynamicModInt構造体
mod が 1000000007 であればよいのですが、そうではない場合もあります。そのような場合に使えるのが DynamicModInt構造体 です。
最初に Mod の値をセットします。あとは StaticModInt構造体 と同じように使うことができます。
|
1 2 3 |
DynamicModInt<int>.Mod = 7; DynamicModInt<int> res = 10; Console.WriteLine(res); // 3 |
E – Throne を解く
問題の概要
円周上に N 個の椅子が並べられている。そのなかにひとつだけ玉座がある。
最初、玉座から時計回りに数えて S 個隣の椅子に座っている。
いま座っている椅子から時計回りに数えて K 個隣の椅子に移動することを繰り返した場合、はじめて玉座に座ることができるのは何回目の行動の後になるか出力せよ。
ただし永遠に玉座に座ることができない場合は -1 を出力せよ。
x 回の行動で玉座に座れることと、S + x * K ≡ 0 (mod N) が成り立つことは同値です。この合同式を満たす最小の x が解です。
S + x * K ≡ 0 (mod N) ⇔ K * x ≡ – S(mod N) と変形できます。この合同式を解くためには、A, B, M の最大公約数 d を求め、A, B, M を d で割ります。このとき A, M が互いに素でなければ解なしです。そうでないときは mod M における A の逆元を B にかけたものが解です。N は固定値ではないので DynamicModInt構造体 を使って解きます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using AtCoder; class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { int[] nsk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nsk[0]; int S = nsk[1]; int K = nsk[2]; // 合同方程式 S + Kx ≡ 0 (mod N) を解く int GCD(int a, int b) => b > a ? GCD(b, a) : (b == 0 ? a : GCD(b, a % b)); int gcd = GCD(GCD(N, S), K); N /= gcd; S /= gcd; K /= gcd; if (GCD(K, N) == 1) { DynamicModInt<int>.Mod = N; DynamicModInt<int> ans = new DynamicModInt<int>(-S); ans /= K; Console.WriteLine(ans); } else Console.WriteLine(-1); } } } |
