D - 動的計画法

時間制限 : 2sec / メモリ制限 : 256MB

(21:52)ジャッジに使われているサンプルテストケースのうち1つのテストケースが問題文のものと異なることが判明致しました。ご不便をおかけして申し訳ありません。なお、テストケース自体は正しいものであるため、リジャッジ等は行いません。ご了承ください。

問題文

高橋君はタテ、ヨコともに 108 マスずつある方眼紙を使って以下の問題を解くことにしました。

「一番左下のマスから開始して、右もしくは上に1マス移動するという操作を繰り返して、各マスにたどり着く方法の個数を 1,000,000,007 で割った余りを求めよ。」

高橋君は動的計画法が好きなので、この問題が動的計画法を使って解けるということにすぐ気づきました。

具体的には

最も左の列もしくは最も下の行に属する全てのマスに 1 を書き込む。まだ整数が書き込まれていないマスについて、左のマスにも下のマスにも整数が書かれていたら、その 2 マスの和を1,000,000,007 で割った余りをそのマスに書き込む。整数が書かれていないマスがなくなるまで操作2を繰り返す。というアルゴリズムによって、答えを求めることが出来ます。

高橋君は上記のアルゴリズムですべてのマスに「左下からたどり着く方法の個数を 1,000,000,007 で割った余り」を書き込みました。

できあがった方眼紙の左下の一部は下図のようになります。

しかし書き込み終わったあと、達成感のために舞い上がってしまい、方眼紙の一部を破いてしまいました。

高橋君の手元には、あるマスと、その上のマスと右のマスの部分のみが書かれている方眼紙の欠片があります。

高橋君はこの欠片を元の位置に戻そうと思ったのですが、方眼紙が大きすぎるので、どこに置けばいいのかわかりません。

欠片の情報から、この欠片が元々の方眼紙の左から何マス、下から何マスの位置にあったのか求めてください。

つまり、左からxマス、下からyマスのマスのことを (x,y) と書くとして、(r,c)、(r,c+1)、(r+1,c)のマスに書かれている整数が与えられるので、 r と c を求めてください。

なお、一番左下のマスは (0,0) です。

Note

タイトル詐欺逆元とmodに気をつける数学の問題 mod の一番良い書き方模索中、　直接overrideしたみ

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long

const ll MOD = 1000000007;

class Num {
    ll value;
public:
    ll operator + (Num obj) {
        return (this->value + obj.value) % MOD;
    }

    ll operator - (Num obj) {
        return (this->value - obj.value + MOD) % MOD;
    }

    ll operator * (Num obj) {
        return (this->value * obj.value) % MOD;
    }
    Num(ll value) { this->value = value; }
};

ll pow(ll a, ll e){
    ll tmp = 1;
    while(e > 0){
        if( e & 1ll){
            tmp = tmp * a % MOD ;
        }
        a = a * a % MOD;
        e >>= 1; 
    }
    return tmp;
}

ll rev(ll n){
    return pow(n, MOD - 2) % MOD;
}

int main(){
    ll s, t, u;
    cin >> s >> t >> u;
    Num a(s), b(t), c(u);

    ll x, y;
    x = c * (b - a);
    x *= rev(Num(a * b) - c * ((b - a)));
    x %= MOD;
    y = b * (c-a);
    y *= rev(Num(a * c) - b * ((c - a)));
    y %= MOD;

    cout << x << " " << y << endl;
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 024 #25

D - 動的計画法

問題文

Note