Q21 本の読み方は何通り？

PHPのソース

<?php
Solve(100, 3); //      834
Solve(180,14); //140615467

class JyoutaiDef
{
    public $RestPageCnt;
    public $MaxPage;
}

function Solve($pTotalPageCnt , $pDayCnt)
{
    //場合の数[ハッシュ値]なDP表
    $wkJyoutai = new JyoutaiDef();
    $wkJyoutai->RestPageCnt = $pTotalPageCnt;
    $wkJyoutai->MaxPage = $pTotalPageCnt;
    $wkHash = GetHash($wkJyoutai);
    $PrevDP = array($wkHash => 1);

    $Answer = 0;
    for($I = 1 ; $I <= $pDayCnt ; $I++){
        $CurrDP = array();
        foreach($PrevDP as $EachHash => $EachVal){
            $wkJyoutai = DeriveJyoutai($EachHash);
            for($J = 1 ; $J <= $wkJyoutai->MaxPage ; $J++){
                $NewJyoutai = new JyoutaiDef();
                $NewJyoutai->RestPageCnt = $wkJyoutai->RestPageCnt - $J;
                if($NewJyoutai->RestPageCnt < 0) break;
                $NewJyoutai->MaxPage = $J - 1;
                $Hash = GetHash($NewJyoutai);
                if(array_key_exists($Hash,$CurrDP))
                    $CurrDP[$Hash] += $EachVal;
                else $CurrDP[$Hash] = $EachVal;
            }
        }
        foreach($CurrDP as $EachHash => $EachVal){
            $wkJyoutai = DeriveJyoutai($EachHash);
            if($wkJyoutai->RestPageCnt == 0)
                $Answer += $EachVal;
        }
        $PrevDP = $CurrDP;
    }
    printf('%dページを%d日以内で読むのは、%d通り' , $pTotalPageCnt , $pDayCnt , $Answer);
    echo PHP_EOL;
}

function GetHash(JyoutaiDef $pJyoutai)
{
    $WillReturn = 0;
    $WillReturn += $pJyoutai->RestPageCnt * 1000;
    $WillReturn += $pJyoutai->MaxPage;
    return $WillReturn;
}

function DeriveJyoutai($pHash)
{
    $WillReturn = new JyoutaiDef();
    $WkMod = $pHash % 1000;
    $WillReturn->RestPageCnt = ($pHash - $WkMod) / 1000;
    $WillReturn->MaxPage = $WkMod;
    return $WillReturn;
}

実行結果

100ページを3日以内で読むのは、834通り
180ページを14日以内で読むのは、140615467通り

解説

場合の数[状態のHash値]
を更新する動的計画法で解いてます。