公式解説

imoscon_o 解説

$P_M-x$ が $998244353$ の倍数となるような $x$ の求め方

このとき，$P_M$ と $x$ の $998244353$ で割った余りはどちらも等しいため，C++の場合は以下のようにして求まります．

$x=(P_M \% 998244353+998244353) \% 998244353$

ちなみに，なぜこのような書き方をしなければならないのかというと，C++は負の数を正の数で割った余りが負の数として返ってきてしまうためです．
なお，Pythonの場合は $P_M$ を $998244353$ で割った余りがそのまま $x$ となるようです．
また，この問題を解くうえで割り算を必要とする過程がありますが，modulo演算において，割り算は特殊な条件を満たさなければ合法な操作として認められません．代わりに逆元を掛け合わせることで期待された効果を得ることができます．ここでは，$998244353$ が素数であることを利用することでフェルマーの最終定理を用いて逆元を高速に求めることができます．

小課題1

Imos操作の逆操作はなにかについて考えます．逆操作とは，Imos操作をした後の数列が与えられたときに，逆操作を行うと元の数列が分かるような操作の事です．
ここで，正整数列 $A=(A_1,A_2,…,A_N)$ に $1$ 度だけImos操作を施した後の数列を $P=(P_1,P_2,…,P_N)$ とおくと，以下の等式が成立します．

$P_1=A_1$
$P_2=A_1+A_2$
$P_3=A_1+A_2+A_3$
$…$
$P_N=A_1+A_2+⋯+A_N$

したがって，$2$ 以上 $N$ 以下の整数 $i$ について，$A_i=P_i-P_{i-1}$ が成立するので，これがImos操作の逆操作に当たります．
これは $O(1)$ で実装できるので，この小課題を解くことができました．
また，これにより逆操作が $1$ つに定まるため，答えるべき数列が $1$ つしか存在しないことの証明も完了します．

小課題2

正でない整数 $i$ について，$A_i=0$ として，以下のことを示します．
数列 $A$ に対して，Imos操作の逆操作を $X$ 回行った後の数列を $P=(P_1,P_2,…,P_N)$ とするとき，
$P_i=\sum_{k=0}^X (-1)^k \cdot {}_X C_k \cdot A_{i-k}$
である．
(証明)
(i) $X=1$ のとき
$B_i=A_i-A_{i-1}$ より成立．
(ii) $X=n$ のとき成立するとして，$X=n+1$ のとき
このとき，

$P_i = (\sum_{k=0}^n (-1)^k \cdot {}_n C_k \cdot A_{i-k}) - (\sum_{k=0}^n (-1)^k \cdot {}_n C_k \cdot A_{i-k-1}) = A_i - ({}_n C_0 + {}_n C_1)A_{i-1} + ({}_n C_1 + {}_n C_2)A_{i-2} - ...$

が成り立つことから，

$P_i=\sum_{k=0}^{n+1} (-1)^k \cdot {}_{n+1} C_k \cdot A_{i-k}$

と変形することができるので，これで題意は示せた．■
したがってこの問題は $O(K)$ で解くことができます．

回答例(C++)

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

const long long mod = 998244353;
long long inverse(long long x) {
	long long ret = 1;
	int y = mod - 2;
	while (y > 0) {
		if (y % 2 == 1) {
			ret = ret * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return ret;
}

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> vec(n);
	rep(i, n) cin >> vec[i];
	long long ans = 0;
	long long pm = 1;
	long long combi = 1;
	rep(i, k + 1) {
		int num = 0;
		if (m - 1 - i >= 0) num = vec[m - 1 - i];
		ans += pm * combi * num;
		ans = (ans % mod + mod) % mod;
		pm *= -1;
		combi = (combi * (k - i)) % mod;
		combi = (combi * inverse(i + 1)) % mod;
	}
	cout << ans << endl;
	return 0;
}
Copy

回答例(Python)

import math
import bisect
import collections
import heapq

mod = 998244353
def inverse(x):
    ret = 1
    y = mod - 2
    while y > 0:
        if y % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        y >>= 1
    return ret

def main():
    n,m,k = map(int,input().split())
    vec = list(map(int,input().split()))
    ans = 0
    pm = 1
    combi = 1
    for i in range(k+1):
        num = 0
        if (m - 1 - i >= 0):
            num = vec[m - 1 - i]
        ans += pm * combi * num
        ans %= mod
        pm *= -1
        combi = combi * (k - i) % mod
        combi = combi * inverse(i + 1) % mod
    print(ans)
    return

main()
Copy