はまやんはまやんはまやん

hamayanhamayan's blog

Sliding Product Sum [CSAcademy #68 E]

https://csacademy.com/contest/round-68/task/sliding-product-sum/

1,2,3,...,Nという数列がある。
この数列の連続するK個以下の部分列の総積の総和をmodMで答えよ。

解法

実は連続する整数の積の和には公式がある。
これを全てのkについて計算するだけの問題。
64ビットを超えた計算を含むので、多倍長整数を使って解こう。
任意のMについて割り算をするのは難しいので、掛ける過程で割ることが出来たら割ってかけよう。
(parse関数などはkenkooooさんの実装を使いました)

using int128 = __int128;
//using int128 = ll;
int128 N, K, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    string s;
    cin >> s;
    N = parse(s);
    cin >> s;
    K = parse(s);
    cin >> s;
    M = parse(s);
    //cin >> N >> K >> M;

    int128 ans = 0;
    rep(k, 1, K + 1) {
        int128 div = k + 1;
        int wait = 1;

        int128 d = 1;
        int128 n = N - k + 1;
        rep(i, 0, k + 1) {
            if (wait and n % div == 0) {
                wait = 0;
                d *= (n / div);
            }
            else d *= n;

            d %= M;
            n++;
        }

        ans += d;
        ans %= M;
    }

    cout << ans << endl;
}