子段乘积(逆元费马小定理)+线段树做法

news/2024/7/5 2:28:49

在这里插入图片描述

题解:一开始做这个题的时候想过尺取法,但是因为没有逆元的知识,不知道该如何不断删除左端元素。其实这题并不难想,设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;
}

后续。。。
刚学会线段树就拿来写了一下这个题目
以上是逆元+尺取法,又现学了一下线段树用线段树莽一波也是不错的解法,本题线段树只涉及了插入和计算“和”的部分

#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  1000000
#define MaxN  0x3f3f3f
#define MinN  0xc0c0c0
typedef long long ll;
using namespace std;
const int mod=998244353;
ll arr[maxn];
ll tree[maxn]={1};
void build_tree(ll node,ll start,ll ends){if(start==ends){tree[node]=arr[start];}else{ll mid=(start+ends)/2;ll left_node=2*node+1;ll right_node=2*node+2;build_tree(left_node,start,mid);build_tree(right_node,mid+1,ends);tree[node]=(tree[left_node]*tree[right_node])%mod;}return ;
}ll query_tree(ll node,ll start,ll ends,ll l,ll r,ll sum){if(r<start||l>ends)  return 1;else if(l<=start&&r>=ends){return (tree[node]*sum)%mod;}else{ll mid=(start+ends)/2;ll left_node=2*node+1;ll right_node=2*node+2;ll sum_left=query_tree(left_node,start,mid,l,r,sum);ll sum_right=query_tree(right_node,mid+1,ends,l,r,sum);return ((sum_left*sum_right)*sum%mod)%mod;}
}
int main()
{int n,m,k;cin>>n>>k;for(int i=0;i<n;i++) scanf("%lld",&arr[i]);build_tree(0,0,n-1);//for(int i=0;i<100;i++)  cout<<tree[i]<<" ";ll imax=0;for(int i=0;i+k-1<n;i++){ll ans;ans=query_tree(0,0,n-1,i,i+k-1,1);imax=max(imax,ans);}cout<<imax<<endl;return 0;}

http://lihuaxi.xjx100.cn/news/286078.html

相关文章

javascript --- 事件托付

javascript 之 事件托付 长处&#xff1a;1、提高性能&#xff08;仅仅须要对父级进行操作&#xff0c;子节点相同会拥有其相关属性和方法&#xff09; 2、对于新加入的事件。也让其拥有父级事件的属性 <!doctype html> <html lang"en"> <head><…

很多程序员编程时都戴耳机?他们在听什么

&#xff08;给视学算法加星标&#xff09;转自&#xff1a;网络听说很多程序员工作时都戴耳机&#xff1f;他们在听什么呢&#xff1f;观点一&#xff1a;非诚勿扰&#xff0c;想静静1、啥也没听&#xff0c;只是带着耳机而已。只是想告诉别人不要打扰我&#xff0c;选择性屏蔽…

线段树 ---- CF452F. Permutation(线段树维护序列Hash)

题目链接 题目大意&#xff1a; 就是给你一个全排列&#xff0c;问你是否存在一个cab2c\frac{ab}{2}c2ab​ 满足ccc的位置在a,ba,ba,b之间 解题思路&#xff1a; 首先我们先按顺序遍历&#xff0c;我们假设遍历到的数是中间那个数就是ccc,那么它要存在的答案的话就是存在一个…

到底是什么特征影响着CNN的性能?

作者 | 刘畅 编辑 | Jane出品 | AI科技大本营&#xff08;ID:rgznai100&#xff09;开门见山。最近阅读了一篇论文&#xff0c;加上看了一些之前的工作。记录一下&#xff0c;CNN 到底学到了什么东西&#xff0c;或者换句话讲。到底是什么样的特征在影响着CNN 的性能&#xff1…

hdu 2896:病毒侵袭

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)            Total Submission(s): 18206 Accepted Submission(s): 4541 Problem Description当太阳的光辉逐渐被月亮遮蔽&#xff0c;世界失去了光明&#xff0c;大地迎来…

poj1548(最小路径覆盖问题)

题意&#xff1a;相当于给出N个坐标点&#xff0c;因为机器人只能向下或者向右走&#xff0c;所以如果能到达其他点&#xff0c;则连接这两个点&#xff0c;即line[i][j]1 最小路径覆盖数: 对于一个DAG&#xff08;有向无环图&#xff09;&#xff0c;选取最少条路径&#xff0…

Prime Path(bfs)广度优先搜索

题目描述 The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now and the…

一些改进模型速度/精度的工程方法

点击上方“视学算法”&#xff0c;选择加"星标"或“置顶”重磅干货&#xff0c;第一时间送达作者&#xff1a;Captain Jackhttps://zhuanlan.zhihu.com/p/92025012本文已由作者授权&#xff0c;未经允许&#xff0c;不得二次转载一些自己的工作经验总结&#xff0c;用…