竞赛讨论区 > c-子段乘积
头像
青柝
发布于 11-05 21:34 湖南
+ 关注

c-子段乘积

#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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐