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; }