ABC024-D:動的計画法

問題

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

タテ、ヨコ 10^8 マスある方眼紙上で頂点 (0, 0) から頂点  (i, j), (i, j+1), (i+1, j) への経路が A\, mod (10^9+7), B\, mod (10^9+7), C\, mod (10^9+7) 通りで与えられる。この時 (i, j) の組み合わせを求めよ。

考え方

グリッドグラフ上で頂点 (0, 0) から (i, j) への経路数は  \displaystyle \frac{(i+j)!}{i! * j!} で与えられる。
同様に (0,0) から (i, j+1) への経路は  \displaystyle \frac{(i+j+1)!}{i! * (j+1)!}(0,0) から (i+1, j) への経路は  \displaystyle \frac{(i+1+j)!}{(i+1)! * j!} 通りである。それぞれ A\, mod (10^9+7), B\, mod (10^9+7), C\, mod (10^9+7) 通りであるから、仮定を整理すると以下が与えられている。

  1.  \displaystyle \frac{(i+j)!}{i! * j!} \equiv A\, mod (10^9+7)
  2.  \displaystyle \frac{(i+j+1)!}{i! * (j+1)!} \equiv B\, mod (10^9+7)
  3.  \displaystyle \frac{(i+1+j)!}{(i+1)! * j!} \equiv C\, mod (10^9+7)

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

 i \equiv (B*C - A*C) * (A*B - B*C + A*C)^{-1} \, mod (10^9+7)  j \equiv (B*C - A*B) * (A*B - B*C + A*C)^{-1} \, mod (10^9+7)

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

 X^{-1} \equiv X^{P-2} \, mod\,P

が成り立つ。よって

 (A*B - B*C + A*C)^{-1} \equiv (A*B - B*C + A*C)^{10^9+5} \, mod (10^9+7)

となる。 (A*B - B*C + A*C)^{10^9+5} は繰り返し累乗法などによってO(logN)で求められる。よって i, j を求めることができた。

       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から問題を見れば見えます。