牛客寒假训练营|牛客寒假训练营 4 C 子段乘积
题目要求 链接：https://ac.nowcoder.com/acm/contest/3005/C
来源：牛客网
题目描述
给出一个长度为 n 的数列 a1,a2,…,ana_1,a_2,\ldots,a_na1?,a2?,…,an?，求其长度为 k 的连续子段的乘积对 998244353 取模余数的最大值。
输入描述:
第一行两个整数n,k。
第二行n个整数,a1,a2,…,ana_1,a_2,\ldots,a_na1?,a2?,…,an?。
输出描述:
输出一个整数，代表最大余数。
示例1
输入
复制
5 3
1 2 3 0 8
输出
复制
6
说明
1?2?3mod??998244353=6123\mod 998244353=61?2?3mod998244353=6
备注:
1≤k≤n≤2?1051 \le k \le n \le 2*10^51≤k≤n≤2?105
0≤ai<9982443530 \le a_i <9982443530≤ai?<998244353
解题思路 【牛客寒假训练营|牛客寒假训练营 4 C 子段乘积】在对数组遍历时，要遇到一种情况，就是子段的长度大于要求的k段时，要除于a[i-k]，又因为对ss取过模，一个取过模的数不能直接除一个数必须取逆元，所以不能简单地相除，逆元可以用费马小定理得到，即a^(p-1）≡1（mod p） 又因为a^(p-2) = （a^(p-1))* a(-1)则a(p-2)≡ a^(-1)（mod p），代码如下：
#include
#include
using namespace std;
#define ll long long
const ll maxn=2e5+7;
const ll mod=998244353;
ll a[maxn];
ll n,k;
ll fema(ll m,ll n){//用快速幂来求m^n
ll sum1=1;
while(n>0){
if(n&1) sum1=(sum1*m)%mod;
m=(m*m)%mod;
n>>=1;
}
return sum1;
}int main()
{
scanf("%lld%lld",&n,&k);
ll i,sum,ss;
i=1;
sum=0;
ss=1;
//所求结果和当前段的乘积
for(int ii=1;
ii<=n;
ii++)
scanf("%lld",&a[ii]);
int nu=0;
//当前段0的个数
for(int i=1;
i<=n;
i++){
if(a[i]==0)nu++;
else ss=(ss*a[i])%mod;
if(i>=k+1){
if(a[i-k]==0) nu--;
//第前K个为0，不在当前段里，nu减掉，ss不用除
else ss=(ss*fema(a[i-k],mod-2))%mod;
//用费马小定理来表示s=s/a[i-k]%mod，因为s取过模，所以无法直接除其他数
}
if(nu==0&&i>=k)//说明当前段长一定为K
sum=max(sum,ss);
}
printf("%lld\n",sum);
return 0;
}
推荐阅读
- 绘本讲师训练营【24期】14/21阅读原创《小黑鱼》
- 绘本讲师训练营【18期】14/21《我的情绪小怪兽》故事会新体验
- 合理情绪疗法之试用｜李克富思维训练营56/90
- 绘本讲师训练营7期9/21阅读原创《蜗牛屋|绘本讲师训练营7期9/21阅读原创《蜗牛屋 》
- 拆书方法训练营
- 2018-09-03(李克富视角点评训练营81/90)|2018-09-03(李克富视角点评训练营81/90) 那只蛙从“井”爬出来又进入了“隧道”
- 学员+3组杨子涓+202002RIA训练营W3D2+苏格拉底提问法
- 绘本讲师训练营【28期】15/21阅读原创《活了100万次的猫》
- 周一（十一）
- 互联网加教育，成就孙慧敏美术梦想