Card Game II (AOJ 0504) - 布の切れ端

もう3月も前のことですが，AOJのVol. 5を埋め終わりました．この問題の解説はあまり見ないので，その記念に書こうと思います．競プロを始めた頃はややこしい数学ゲーという印象がありましたが，意外とすっと解けます．

問題

解法

ゲームで引く順番にカードを並べると数列が1つ得られます．ちょうど $m$ 回の再開で成功したとき，この数列がどうなっているかを考えます．

$m = 0$ のとき

最初に山 $1$ のカードを引いた後，山 $i$ からカードを引くためには数 $i$ が書かれたカードを引く必要があります．そのため，山 $1$ のカードをすべて引くにはそれより1枚少ない枚数の $1$ の書かれたカードを引く必要があり，山 $i \ (i \ge 2)$ のカードをすべて引くにはそれと同じ枚数の $i$ の書かれたカードを引く必要があります．その後，その山でゲームを終了するには同じカードをさらに1枚引く必要があります．ゲーム開始時，数 $i$ が書かれたカードは山 $i$ のカードと同じ枚数しかなかったので，2番目以降の山でゲームを終了するにはカードが足りません．したがって，最後に引いたカードには $1$ が書かれています．

$m = 1$ のとき

同様の考察から失敗する直前に引いたカードには $1$ が書かれていることが分かります．これは山 $1$ からカードを引こうとして失敗したことを意味するので，山 $1$ のカードと $1$ の書かれたカードは失敗するまでにすべて引かれています．山 $i \ (i \ge 2)$ のカードと数 $i$ が書かれたカードについては引いた枚数が同じなので，残る枚数も同じです．特に再開後最初にカードを引いた山の番号を $b \ (b \ge 2)$ とすると，山 $i \ (2 \le i < b)$ のカードはすべて引かれているので， $i$ の書かれたカードもすべて引かれています．ゲーム再開時の山 $i$ のカードと数 $i$ が書かれたカードの残り枚数は同じなので，最初と同じ考察ができて，ゲームの最後に引いたカードには $b$ が書かれていることが分かります．

以上により，ゲームで得られる数列は

$m = 0$ のとき：最後は $1$ で終わる（条件1）
$m = 1$ のとき： $2$ 以上 $n$ 以下の整数 $b$ が存在し， $b$ 未満の数の中で最も後ろにあるのは $1$ で，最後は $b$ で終わる（条件2）

を満たすことが分かりました．

逆にこれらの条件を満たす数列からその数列が得られるちょうど $m$ 回の再開で成功する配置を作ることができます．例えば，条件1を満たす数列が与えられたとき，1番目の数が書かれたカードを山 $1$ に置き，2番目以降の数が書かれたカードをその直前の数の山に置くことで，再開なしで成功する配置が得られます．この対応は1対1対応なので，条件1，2を満たす数列を数えればよくなります．

条件1を満たす数列の個数 $C$ は

$\begin{align*}C = \frac{(nk-1)!}{(k-1)!(k!)^{n-1}}\end{align*}$

です．

各 $b = 2, 3, \dots, n$ に対して，条件2を満たす数列の個数 $C_{b}$ は

$\begin{align*}C_{b} = \frac{(nk-1)!}{((b-1)k)!(k-1)!(k!)^{n-b}} \cdot \frac{((b-1)k-1)!}{(k-1)!(k!)^{b-2}} = \frac{(nk-1)!}{(b-1)(k-1)!(k!)^{n-1}} = \frac{C}{b-1}\end{align*} \$

です．これは $b$ 未満の数をまとめて扱い，その後で分けて扱うことで得られます．

可能な配置は $(nk)! / (k!)^{n} = nC$ 個あります．

最後に簡単な計算をすることで，求める確率が

$m = 0$ のとき： $1 / n$
$m = 1$ のとき： $1 / n + \sum_{b=2}^{n} 1 / ((b-1)n)$

であることが分かります．

#include <bits/stdc++.h>

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

template <int r>
struct Decimal{
    std::vector<int> digits;
    
    Decimal(int n) : digits(r + 1, 0) { // 1/n
        int rem = 1;
        for(int i=1;i<=r;++i){
            rem *= 10;
            digits[i] = rem / n;
            rem %= n;
        }
    }

    Decimal<r>& operator+=(Decimal<r> &rhs){
        for(int i=r;i>0;--i){
            digits[i] += rhs.digits[i];
            if(digits[i] >= 10){
                digits[i] -= 10;
                digits[i - 1] += 1;
            }
        }

        return *this;
    }
};

constexpr int r = 10100;

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    while(true){
        int N, K, M, R;
        std::cin >> N >> K >> M >> R;

        if(N == 0){
            break;
        }

        Decimal<r> p(N);

        if(M == 1){
            for(int k=1;k<=N-1;++k){
                Decimal<r> d(k * N);
                p += d;
            }
        }

        std::cout << p.digits[0] << ".";
        for(int i=1;i<=R;++i){
            std::cout << p.digits[i];
        }
        std::cout << std::endl;
    }
}