ABC024-D：動的計画法

問題

https://beta.atcoder.jp/contests/abc024/tasks/abc024_d

タテ、ヨコ マスある方眼紙上で頂点 から頂点 への経路が 通りで与えられる。この時 の組み合わせを求めよ。

考え方

グリッドグラフ上で頂点 から への経路数は で与えられる。
同様に から への経路は 、 から への経路は 通りである。それぞれ 通りであるから、仮定を整理すると以下が与えられている。

1. 
2. 
3. 

(1)と(2)、(1)と(3)をうまく組み合わせて について解くと以下のようになる。（計算は省略）

フェルマーの小定理より、ある数 の法を取る数 が素数であるとき

が成り立つ。よって

となる。 は繰り返し累乗法などによってで求められる。よって を求めることができた。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long MOD = 1000000007;
            long A = in.nextLong() % MOD;
            long B = in.nextLong() % MOD;
            long C = in.nextLong() % MOD;
            long AB = A * B % MOD;
            long BC = B * C % MOD;
            long AC = A * C % MOD;

            long r = (BC - AC + MOD) % MOD * power((AB - BC + AC + MOD), MOD-2, MOD);
            long c = (BC - AB + MOD) % MOD * power((AB - BC + AC + MOD), MOD-2, MOD);

            out.printf("%d %d\n", r % MOD, c % MOD);
        }

        long power(long a, long e, long modP) {
            long ret = 1;
            for (; e > 0; e /= 2) {
                if (e % 2 != 0) {
                    ret = (ret * a) % modP;
                }
                a = (a * a) % modP;
            }
            return ret;
        }

ポイント

• MOD上の割り算

類題

雑記

余談ですが、過去のABCの問題を解く際に、画像ファイルのURLがNotFoundになって見えないことがありました。これはbeta版ではないURLから問題を見れば見えます。