#include<iostream>
typedef long long ll;
using namespace std;
const ll p = 998244353;
ll v[200005];
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){
if(b==0){
d = a; x = 1; y = 0;
return;
}
ex_gcd(b,a%b,d,y,x);
y -= x*(a/b);
}
ll inv(ll a){
ll d, x, y;
ex_gcd(a,p,d,x,y);
return (x%p+p)%p;
}
// 求子段[l, r)中长度为k的最大乘积
ll check(int l, int r, int k){
if(r-l<k)return -1;
ll res = 1;
for(int i=l;i<l+k;++i)res = res*v[i]%p;
for(int i=l+k;i<r;++i){
res = max(res, (res*inv(v[i-k])%p)*v[i]%p);
}
return res;
}
int main(){
int n, k;
cin >> n >> k;
int t = -1;
ll res = 0;
for(int i=0;i<n;++i){
cin >> v[i];
if(v[i]==0){ // 以0为分界线 将数组分为若干个子段
res = max(res, check(t+1, i, k));
t = i;
}
}
cout << max(res, check(t+1, n, k)) << endl;
return 0;
}
我的代码哪里有问题吗?求大佬指点
全部评论
(3) 回帖