泛型编程与 OI——modint

阅读: 评论:0

泛型编程与 OI——modint

泛型编程与 OI——modint

简介:大家好,我是枫哥🌟一线互联网的IT民工、📝资深面试官、🌹Java跳蚤网课堂创始人。拥有多年一线研发经验,曾就职过科大讯飞、美团网、平安等公司。在上海有自己小伙伴组建的副业团队,目前业余时间专注Java技术分享,春招/秋招/社招/跳槽,一对一学习辅助,项目接活开发。

🎉🎉扫码左侧二维码,加入群聊,一起学习,一起进步!

🌟 欢迎关注 🌟 收藏 🌹留言 🌹

🍊🍊:文末送福利

目录

背景介绍

过去的做法

第一种 直接取模

第二种 函数取模

泛型编程


 

在 OI 中,有大量的题目要求对一些数字取模,这便是本文写作的背景。

背景介绍

这些题目要么是因为答案太大,不方便输出结果,例如许多计数 dp;要么是因为答案是浮点数,出题人不愿意写一个确定精度的 Special Judge,例如很多期望概率题;要么是因为这道题目直接考察了模的性质和运用,比如大量的 998244353 类的多项式题目。

过去的做法

在这种要求之下,取模运算就成为了编程中不可缺少的一部分。下面以式子 ans=(x+y+z)×uans=(x+y+z)×u 为例介绍几种写法。

第一种 直接取模

这种方法是直接取模,简单直接,清晰明了。

constexpr int p=998244353;int ans=1ll*(((x+y)%p+z)%p)*u%p;

但是这种方法有着严重的缺陷,一是容易忘记大括号,二是容易中间运算时搞错运算顺序、忘记取模,三是式子太长、括号太多、不易检验。

因此,不推荐运用这种方法。

第二种 函数取模

这种方法有效地解决了直接取模的忘记取模的漏洞。

constexpr int p=998244353;int add(int a,int b){return a+b>=p?a+b-p:a+b;
}int sub(int a,int b){return a<b?a-b+p:a-b;
}int mul(int a,int b){return 1ll*a*b%p;
}int ans=mul(add(add(x,y),z),u);

 但是,这种写法的式子依旧太长,不易检验,并且如果编译器没有任何优化(现在不存在这种情况了)的话,大量的函数调用将会耗费不少的时间。并且如果要对多个模数取模,则需要写多个函数,显得代码冗长。

泛型编程

考虑到函数取模的优点,我们不妨通过类的运算符重载来进一步优化 add 等函数。

同时为了解决多个模数的问题,我们考虑泛型编程,将模数直接包含在类型中。

template<typename T,const T p>
class modint{private:T v;public:modint(){}modint(const T& x){assert(0<=x&&x<p);v=x;}modint operator+(const modint& a)const{return v+a.v>=p?v+a.v-p:v+a.v;}modint operator-(const modint& a)const{return v<a.v?v-a.v+p:v-a.v;}modint operator*(const modint& a)const{return 1ll*v*a.v%p;}T operator()(void)const{return v;}
};modint<int,998244353> x(),y(),z(),u();
modint<int,998244353> ans=(x+y+z)*u;

这样使用的时候,一方面减少了心智负担,不用操心运算时忘记取模;另一方面采取了常数更小的加减法操作,运算更快。

唯一的缺点就是类型名难写,但是模数个数少的时候可以缩写,即写成:

typedef modint<int,998244353> modInt1;

 这样就解决了类型名长的缺点。

🌹 🌹感谢大家,坚持看完,既然选择了这条路,那就一起加油,一起学习!如果需要学习资源,实战面试资料,项目资源。关注公众号:IT枫斗者,🌟根据关键字领取对应的资料福利🌟!咨询解决问题,公众号私聊枫哥,备注来意。

🍊回复:java全套学习资源

🍊回复:面试资料

🍊回复:枫哥简历

🍊回复:程序员表白神器               

(从此告别程序员单身狗!)

🍊回复:程序员兼职网站

🍊回复:枫哥666                             

( 获取66套项目实战资料,大厂面试视频)

本文发布于:2024-01-28 14:42:57,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/17064241818162.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:OI   modint
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23