問題

感想

フェルマーの小定理と繰り返し二乗法を使った。
とてもためになった問題でした。
昔のC問題むずすぎないか....笑

考え

フェルマーの小定理 $a^{p} \equiv a$ $（modp）$ を利用します。 $(p = 1000000007)$

$x = 3, y = 3$ のときは，求める解は組み合わせを考えて $_{x - 1 + y - 1} C _{y - 1}$ となります（これを $\displaystyle \frac{s}{t}$ とします）。このとき，割る動作を行わなければいけません。割る動作は $x, y$ が十分に大きくない時にはできるのですが，大きくなるとオーバーフローを招いてしまいます。分子を先に $modp$ で考えておくことができなくなるからです。

つまり，割る動作を行うとすると

分子を求める（この時 $modp$ で考えれない）
分子の値を割っていく
最後に $p$ で割ってその時の余りが答えとなる

ということになるのですが，最初の分子を求める過程でオーバーフローしてしまうでしょう。この分子の値を割るという動作をしないで解を求める時に使うのがフェルマーの小定理です。

フェルマーの小定理は， $a, p$ が互いに素であるとき， $a^{p-1} \equiv 1$ となります。つまり，

$\displaystyle \frac{s}{t} × 1 \equiv \displaystyle \frac{s}{t} × a^{p - 1}$

となります。ここで $a = t$ とすれば割る動作をなくすことができます。 $s × t^{p - 2}$ の $p$ での余りを求めれば解を得ることができるのです。 $t^{p - 2}$ の求め方については繰り返し二乗法を用いましょう。

Accepted Program

#include <iostream>
#define ll long long
#define mod 1000000007
using namespace std;

ll db (ll x, ll y) {
  // xをy乗する
  if (y == 1) {
    return (x % mod);  
  }
  if (y % 2 == 0) {
    ll sub = (db(x, y / 2) % mod);
    return ((sub % mod) * (sub % mod)) % mod;
  }  
  else {
    return ((x % mod) * (db(x, y - 1)) % mod) % mod;  
  }
}

int main () {
  ll w, h;
  cin >> w >> h;
  w = w - 1;
  h = h - 1;
  if (h > w) {
    swap(h, w);  
  }
  ll ans = 1;
  ll sub = 0;
  
  // (w + h) C (h)
  // 1. 分母
  for (ll i = 0; i < h; i++) {
    sub = w + h - i;
    ans = ((ans % mod) * (sub % mod)) % mod;
  }   
  // 2. 分子
  sub = 1;
  for (ll i = 1; i <= h; i++) {
    sub = ((sub % mod) * (i % mod)) % mod;    
  }
  // cout << ans << " " << sub << endl;
  // return 0;
  sub = db(sub, mod - 2);
  cout << ((ans % mod) * (sub % mod)) % mod << endl;
}

プログラミング備忘録

日頃のプログラミングの成果をここに書いていきます．

C - 数式の書き換え〜ABC033〜

問題

感想

考え

Accepted Program