【牛客】3005 C-サブセグメント積

リンク:https://ac.nowcoder.com/acm/contest/3005/C出典:牛客網
タイトルの説明
長さnの数列a 1,a 2,...,anを与え,その長さkの連続サブセグメントの積対998244353の型取り残数の最大値を求めた.
説明を入力:

       n,k。
   n   ,a1,a2,…,an。

出力の説明:

      ，      。

例1
入力

5 3
1 2 3 0 8

しゅつりょく

6

説明

1∗2∗3mod  998244353=6

コメント:
1 ≤ k ≤ n ≤ 2 ∗ 1 0 5 1\leq k\leq n\leq 2* 10^5 1≤k≤n≤2∗105
0 ≤ a i < 998244353 0≤ai<998244353 0≤ai<998244353
問題解
尺取法を用いて解くとsumはk個数積の残数を保持しているが,後移時にはk個数の最初の数を除去する必要があり,ここではフェルマの小定理に基づいて乗算逆元を求める必要があり,直接除去することはできない.
注意すべきは、rが0にスキャンされると、lを直接0の次のビットに移動することである.
コード#コード#

#include
#include
using namespace std;
typedef long long ll;

ll mod=998244353;
ll a[200005];
ll sum=1,maxx=0;

ll power(ll a,ll b){
	ll c=1;
	for(;b;b>>=1){
		if(b&1)
			c=c*a%mod;
		a=a*a%mod;
	}
	return c;
}

int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	ll l=1,r=1;
	while(r<=n){
		if(a[r]){
			sum=(sum*a[r])%mod;
			if((r-l+1)%k==0){
				maxx=max(maxx,sum);
				sum=sum*power(a[l],mod-2)%mod;
				l++;
			}
		}
		else{
			l=r+1;
			sum=1;
		}
		r++;
	}
	cout<