子段乘积

子段乘积
https://ac.nowcoder.com/acm/contest/3005/C

逆元：拓展欧几里得、费马小定理
maxn初始值应设为0

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;

void extern_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    extern_gcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extern_gcd(a, m, x, y);
    return (m + x % m) % m;
}
int n, k;
int zero[N];
ll a[N], maxn = 0;

int main() {
    scanf("%d %d", &n, &k);
    int ans = 1;
    zero[0] = -1;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        if (!a[i])
            zero[ans++] = i;
    }
    zero[ans] = n;

    for (int i = 0; i < ans; i++) {
        int start = zero[i] + 1, end = zero[i + 1] - 1;
        int len = end - start + 1;
        ll sum = 1;
        if (len < k) continue;
        for (int j = start; j < start + k; j++) {
            sum = (sum * a[j]) % mod;
        }
        if (maxn < sum) maxn = sum;
        for (int j = start + k; j <= end; j++) {
            sum = sum * mod_inverse(a[j - k], mod);
            sum %= mod;
            sum = sum * a[j];
            sum %= mod;
            if (sum > maxn)
                maxn = sum;
        }
    }
    cout << maxn << endl;
}