牛客網子段乘積

子段乘積

添加連結描述

看了很多算法題解，對于小白的我來說，都看得不是很懂，是以往往看了别人的代碼，還要自己整理一遍思路，現在把我寫的一些注釋分享給大家，大家一起學習！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll quick(ll a,ll b)//快速幂 快速幂的疊代寫法
{
    ll ret=1;
    while(b)
    {			//是以當b 為奇數時 b & 1 傳回為1，if條件成立，這樣執行速度更快 
        if(b&1)//是以可以用if ((b & 1) == 0)代替if (b % 2 == 0)來判斷a是不是偶數 
			ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;//操作數每右移一位，相當于該數除以2。 右移 
    }
    return ret;
}
/*（1）初始令ans = 1,用來存放累積的結果。

（2）判斷b的二進制末尾是否為1 ，（及判斷 b&1 是否為 1），也可以了解為判斷b 是否為奇數。如果是的話，令ans乘上a的值。

（3）令a平方，并使b右移一位，（也可以了解為，b/2）

（4）隻要b 大于0，就傳回（2）。
*/

ll inv(ll a){
	return quick(a,mod-2);//a的mod-2次方 
}

typedef vector<int> vi;
int main()
{
    ll ans=0;
    int n,k;
    cin>>n>>k;
    int zero=0;
    ll cur=1;
    vi a(n);//定義一個vi容器，大小為n，命名為a 
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(!a[i]) 
			zero++;//零加一 
        else 
			cur=cur*a[i]%mod;//非零相乘取模 
        if(i>=k)//i大于連續子段長度 
        {
            if(!a[i-k]) 
				zero--;//零減一 
            else //inv(a[i-k])表示a[i-k]的mod-2次方 
				cur=cur*inv(a[i-k])%mod;//如果初始值a大于mod，那麼需要在進入函數前就讓a對mod取模，
        }
        if(i>=k-1&&!zero) //zero==0,滿足條件       
			ans=max(ans,cur);
    }
    cout<<ans<<'\n';
    return 0; 
}
           

希望對大家有幫助，嘻嘻！