2020牛客寒假算法基础集训营4 C题.子段乘积

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0)

// *start on @date: 2020-02-11 14:32

ll dx[] = {0, 0, 1, -1};
ll dy[] = {1, -1, 0, 0};

const ll N = 2e5 + 5;
const ll mod = 998244353;
ll a[N];
ll sum[N];
ll n, k;
ll pow_mod(ll a, ll b, ll p)
{ //a的b次方求余p
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}
ll sol(ll l, ll r)
{
    if (r - l + 1 < k)
        return 0;
    if (l > r)
        return 0;
    ll cnt = 0;
    sum[0] = 1;
    for (ll i = l; i <= r; i++)
    {
        cnt++;
        sum[cnt] = sum[cnt - 1] * a[i] % mod;
    }
    ll ans = 0;
    for (ll i = k; i <= cnt; i++)
    {
        ll t = sum[i] * pow_mod(sum[i - k], mod - 2, mod) % mod;
        ans = max(ans, t);
    }
    return ans;
}
int main()
{
    cin >> n >> k;
    ll ans = 0;
    ll cnt = 0;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] == 0)
        {
            ans = max(ans, sol(i - cnt, i - 1));
            cnt = 0;
        }
        else
            cnt++;
    }
    if (cnt > 0)
        ans = max(ans, sol(n - cnt + 1, n));
    cout << ans << endl;
    return 0;
}