メタプログラミングによるべき和計算

図書館で借りてほったらかしにしてあった（他の本を読んでいた）「数学ガール」を今日読み出した。

作者: 結城浩
出版社/メーカー: SBクリエイティブ
発売日: 2007/06/27
メディア: 単行本
購入: 58人クリック: 1,055回
この商品を含むブログ (967件) を見る

ざーっと読んで、カタラン数の章。この問題、カタラン数であることに気がつくのに時間がかかった。10分くらいかかったかも。答えあわせとして、主人公の思考過程を読んでいて、漸化式が出てきたところで、なぜかタイトルの問題を思いついた。

べき和とは、



S_n(m) = 1ⁿ + ... + mⁿ

である。これを、



cout << S<3>(4) << endl;

こんな具合に求めたい。

$(m+1)^n = \sum_{l=1}^{m+1}{l^n} - \sum_{l=1}^m{l^n} = \sum_{l=1}^m{((l+1)^n-l^n)}+1$
$= \sum_{l=1}^m{\sum_{k=1}^{n-1}{_nC_kl^k}} + 1 = \sum_{k=1}^{n-1}{_nC_k\sum_{l=1}^m{l^k}} - 1$
$= \sum_{k=1}^{n-1}{_nC_kS_k(m)} + 1$

より、

$nS_{n-1}(m) = (m+1)^n - \sum_{k=1}^{n-2}{_nC_kS_k(m)} - 1$

また、

$T_{n-1,l}(m) \equiv (m+1)^n - \sum_{k=1}^{l-1}{_nC_kS_k(m)} - 1$

とおけば、

$T_{n,0}(m) = (m+1)^{(n+1)} - 1$
$T_{n,l}(m) = T_{n,l-1} - _{n+1}C_{l-1}S_{l-1}(m)$

これで、コード化できる。



#include 
using namespace std;
template

struct C {

    enum { value = C::value * (n - m + 1) / m };

};
template

struct C {

    enum { value = 1 };

};
template

int Pow(int m) {

    return Pow(m) * m;

}
template<>

int Pow<0>(int m) {

    return 1;

}
template

struct cPowSum {

    int operator()(int m) {

        return cPowSum()(m) - S(m) * C::value;

    }

};
template

struct cPowSum {

    int operator()(int m) {

        return Pow(m + 1) - 1;

    }

};
template

int S(int m) {

    return cPowSum()(m) / (n + 1);

};
int main() {

    cout << S<0>(1) << endl;    // 1

    cout << S<3>(4) << endl;    // 100

    cout << S<8>(10) << endl;   // 167731333

}