以下、\(x\) を含む式は全て形式的べき級数であるとします。

オイラーの五角数定理

オイラーの五角数定理 (pentagonal number theorem) とは、次のような定理です。

\[\displaystyle \prod_{i=1}^{\infty} (1-x^i) = \sum_{n=-\infty}^{\infty} (-1)^nx^{\frac{n(3n-1)}{2}}\]

証明はここでは省略します。気になる方は wikipedia (https://en.wikipedia.org/wiki/Pentagonal_number_theorem) 等をご参照ください。

本問題の解法

求める値は、次の式で表されます。

\[[x^M]\ \prod_{i=1}^{N} (x+2x^2+3x^3+\dots+ix^i+ix^{i+1}+ix^{i+2}+\dots)\]

総積記号の中身を変形すると、

\[[x^M]\ \prod_{i=1}^{N} \frac{x(1-x^i)}{(1-x)^2}\]

と表すことができます（ここの部分の導出方法は後述）。

さらに変形をすると、

\[ \begin{aligned} [x^M]\ \prod_{i=1}^{N} \frac{x(1-x^i)}{(1-x)^2} &= [x^{M-N}]\ \prod_{i=1}^{N} \frac{(1-x^i)}{(1-x)^2}\\ &= [x^{M-N}]\ \frac{\prod_{i=1}^{\infty} (1-x^i)}{(1-x)^{2N}} \end{aligned} \]

（最後の式変形において \(M-N \leq N\) を用いた）

となり、冒頭に紹介したオイラーの五角数定理における左辺の式がそのまま分子に現れます。よって、分子の無限積を展開した際に出てくる項のうち、次数が \({M-N}\) 以下であるものは \(O(\sqrt{N})\) 個しかありません。それらを \(a_1 x^{e_1},a_2 x^{e_2},\dots,a_k x^{e_k}\) とおくと、

\[ \begin{aligned} [x^{M-N}]\ \frac{\prod_{i=1}^{\infty} (1-x^i)}{(1-x)^{2N}} &=[x^{M-N}]\ \frac{\sum_{i=1}^{k} a_kx^{e_k}}{(1-x)^{2N}}\\ &=\sum_{i=1}^{k} a_k \binom{M+N-{e_k}-1}{2N-1} \end{aligned} \]

となり、二項係数の計算に Lucas の定理を用いることで、\(O(\sqrt{N}\log_{\text{mod}}{N} +\text{mod})\) でこの問題を解くことができます。

「ここの部分の導出方法は後述」と書いたところについて

このような形のべき級数は、係数列の階差数列を考えることで簡潔な分数式表現を得られることが多いです。また、係数列の階差数列を取ることは、形式的べき級数において \((1-x)\) をかけることに該当します。実際に、

\[f_i(x) = (x+2x^2+3x^3+\dots+ix^i+ix^{i+1}+ix^{i+2}+\dots)\]

とおくと、

\[f_i(x)(1-x) = (x+x^2+x^3+\dots+x^i)\]

\[f_i(x)(1-x)^2 = (x-x^{i+1})\]

となるため、

\[f_i(x) = \frac{x(1-x^i)}{(1-x)^2}\]

です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using mint = modint;

const int mod = 200003;

mint fact[mod];
mint ifact[mod];

// binom(n, k) mod 200003
mint binom(ll n, ll k) {
    if (k < 0 or k > n) return 0;
    mint res = 1;
    while (n) {
        ll n0 = n % mod;
        ll k0 = k % mod;
        if (n0 < k0) return 0;
        res *= fact[n0] * ifact[k0] * ifact[n0 - k0];
        n /= mod;
        k /= mod;
    }
    return res;
}

int main() {
    mint::set_mod(mod);
    fact[0] = 1;
    for (int i = 1; i < mod; i++) fact[i] = fact[i - 1] * i;
    ifact[mod - 1] = fact[mod - 1].inv();
    for (int i = mod - 1; i >= 1; i--) ifact[i - 1] = ifact[i] * i;
    
    ll n, m;
    cin >> n >> m;
    
    mint ans = 0;
    for (ll i = 0; i * (3 * i + 1) / 2 <= m - n; i++) {
        ll j = i * (3 * i + 1) / 2;
        ans += binom(m + n - j - 1, 2 * n - 1) * (i % 2 ? -1 : 1);
    }
    for (ll i = 1; i * (3 * i - 1) / 2 <= m - n; i++) {
        ll j = i * (3 * i - 1) / 2;
        ans += binom(m + n - j - 1, 2 * n - 1) * (i % 2 ? -1 : 1);
    }
    cout << ans.val() << endl;
}