子段乘积(逆元费马小定理)
程序员文章站
2022-07-13 13:46:51
...
题解:一开始做这个题的时候想过尺取法,但是因为没有逆元的知识,不知道该如何不断删除左端元素。其实这题并不难想,设l,r为两端开始都置为1,当长度小于k的时候不断乘右端元素并取余,当长度等于k时删除左端元素并且乘上右端端元素。注意:若右端元素为0时,就将两个端点都移到下一位从新开始。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#define maxn 110
#define MaxN 0x3f3f3f
#define MinN 0xc0c0c0
typedef long long ll;
using namespace std;
const int mod=998244353;
ll a[300010];
ll quickpow(ll a,ll b){
ll ans=1;
while(b){
if(b%2==1)
ans=ans*a%mod;
a=a*a%mod;
b=b/2;
}
return ans;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll l=1,r=1;
ll imax=0;
ll sum=1;
while(r<=n){
if(r-l<k-1&&a[r]!=0){
sum=(sum*a[r])%mod;
r++;
}
else if(r-l==k-1&&a[r]!=0){
sum=(sum*a[r])%mod;
imax=max(imax,sum);
r++;
}
else if(r-l==k&&a[r]!=0){
sum=(sum%mod*a[r]%mod*quickpow(a[l],mod-2))%mod;
l++,r++;
imax=max(imax,sum);
}
else if(a[r]==0){
r++;
l=r;
sum=1;
}
}
cout<<imax<<endl;
return 0;
}
上一篇: 数论之同余与逆元