上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化
计算a%m时,如果m能小一些的话,通常计算起来就会方便很多
比如可以用更小的内存进行预处理,或者找到循环节之类的很好的东西
在做了Project Euler 330后深刻的感受到了这点…
题中要求对77777777取模,可以看到这和平时常用的对某个质数取模不同,这回是个合数
77777777 = 7 * 11 * 73 * 101 * 137
在过去,看到要对合数取模感觉就不太爽,因为有些性质只有质数才能用,比如组合数取模
这题搞了很久没有进展才想起来还有个剩余定理
对于两两互质的一组整数{m1,m2,…,mn}
设m=m1*m2*…*mn, 也就是m是这组数的乘积
设bi=a%mi, 也就是bi是a对mi取余的余数
已知{b1,b2,…,bn}的话,可以求得a%m
具体做法是找到ci=(m/mi)*k使得ci%mi==1
因为两两互质,所以k只要枚举1~mi-1就一定能找到满足条件的ci
最后a%m=sum{ci*bi}%m
因此当m可以分解质因数时可以分成两两互质的一组数,然后通过计算bi来得到a%m
这样做有2个好处
一个是有可能得到mi是质数,可以应用质数所特有的方法
另一个是模数小了,这样如果有循环节的话就更容易发现,这就更爽了
tags: 模板 author: ben1222 comments: 1 Comment
本想在寒假期间写点什么的…无奈域名出了点问题…
导致这一个半月里面网站一直处于无法访问的状态…
想起以前积累的计算几何模板…想差不多可以整理下发出来…
不过充斥着define…以及define的奇怪用法…可以说完全是C语言风格的代码…
总之这是一个基于数组和define而不是类和template的模板…会有人看吗…
如果每段代码都注解出一步步怎么得到的话…工程浩大…
结果心血来潮…给几乎每段代码画了个图片…
蓝色是已知,红色是所求…
画了几个才发现…有些还真难用图片表达啊…
那么就开始吧…
tags: 图片, 心血来潮, 模板 author: ben1222 comments: 6 Comments
昨天是ZOJ Monthly, August 2010
好久没做题了…N天前就看到这次月赛是东方专场…于是想着一定要去凑凑热闹…
不过最后还是只做了4个小时…最后一小时忙别的事情去了…
一看题数…居然有13题…
题号也变成了各种人物的名字了…
一上来是第阿求题…禁语吗……glob和regex的转换…看了下样例感觉不难…但是害怕有一堆要考虑的东西…
然后是第⑨题…算术教室…n个人围成一圈随机选取m个人,其中有9人是连着坐的概率是多少呢?…第一反应就是感觉是组合数方面的于是无视中…
然后看到已经有人过题了…第妖梦题…为大胃王幽幽子准备食物…第i天能准备bi份食物,但是要吃掉ai份食物…希望食物越新鲜越好…求各天准备多少食物…果然很水呢…从后往前扫一遍就可以了…
本想就看看题目娱乐下…结果一不小心手痒了…
于是敲了下…过了…
接着发现又一题有人过了…第四季题…黑白分明呢…用了Bad Apple影绘的图…
把24位点阵图转换成灰度然后再根据公式二值化…也很水…看到那句”All divisions are truncated divisions.”后就想…会有人栽在这里吧…后来真发现有个id是”一句All divisions are truncated divisions. 让我wa了10次，杯具了整个下午！！！”
但是敲了一下…在本地测试的时候用scanf(“#%2lx%2lx%2lx”,&r,&g,&b);来读入,结果本地测试死循环了…难道#也是特殊字符?于是改成了scanf(“%#%2lx%2lx%2lx”,&r,&g,&b);在本地测试通过了…可是交上去OLE了…难道编译器不同吗…
于是很郁闷的改成了scanf(“%s”,str);sscanf(str+1,”%2lX%2lX%2lX”,&r,&g,&b);
题目描述里面没说输出的9或者空格之间需要空格隔开…但是sample output里面却隔开了…于是改成没有空格隔开结果wa了…
最后再改回来有空格隔开的才AC…
接着看到第灵梦题有人过了…塞钱箱…说是第i天请人赛钱可以得到si元,但是如果这么做了,下一次请人赛钱的时间必须在xi天后,yi天前…求如果第一天请人赛钱的话,最多能得到多少钱…
稍微想了下,一个简单的dp而已…dp[i]表示第i天请人赛钱的话,从第i天开始最多能得到多少钱…转移时只要找xi天后,yi天前这段区间的dp值最大的即可…
然后一看规模…5万天…囧了…不过求区间最大值而已…解题报告虽然说用线段树…可当时我想到的却是rmq…
但是rmq是一次性的预处理的…于是就YY着改造了一下,依然沿袭rmq那种思路:分成logN层,每层有N个数,第i层的第j个数表示在[j,j+2^i-1]的范围内最大值是多少
然后从后往前边dp边insert,对于第i天来说,这天之后的每一天的dp值和rmq数组值都是已经得到了的,于是就能得到第i天的dp值,然后将这个值插入进rmq数组,更新第i个数的那logN层数字,总复杂度O(nlogn)
很快写好了…提交却下标越界…然后发现数组开小了- -|||…改后AC
在看解题报告的时候发现评论里有说Sparse Table什么的…原来我那方法叫这个名字啊…
接下来看到第辉夜题有人过…妹红要埋伏辉夜吗…题目是求一张图上从起点到终点之间的必经之路…也就是桥?…模板题吗…可惜我只有割点的模板…于是忽略了这题…
接下来看到第芙兰题有人过了…永夜抄吗……看到迷途竹林以为又是图论有关的…结果却不是这样…
一共有n个房间,第i个房间有xi个ITEM,每个是ai点,有yi个TIME,每个是bi点,每次去一个房间把所有这个房间的ITEM和TIME收完回到入口,直到所有房间的ITEM和TIME都收完…
拿一个点数是a的ITEM的时候可以得到IV分,并且TV增加a
拿一个点数是b的TIME的时候可以得到TV分,并且IV增加b
一开始IV和TV值为0,求最多能得到多少分
因为进一个房间后,该房间所有的ITEM和TIME都要收完,所以先考虑在一个房间内的情况,该按什么顺序收最好
小数据手动演算了一下,发现分数会增加IV*xi+TV*yi+u*ai+v*bi,并且u+v=xi*yi,并且对任何正整数的u,v搭配都总有一种顺序可以满足
于是得到了在第i个房间内最多分数会增加IV*xi+TV*yi+max{ai,bi}*xi*yi的结论,可见ai,bi和IV,TV是分离的,因此外面用一层状态压缩dp计算2^15个状态就可以了
dp[state]表示state的位为1的对应的房间已经去过的情况下,所得到的最大分数
并且这个情况下的IV和TV值是固定的,轻轻松松的上吧…
又看到第因幡题有人过…腹黑兔啊…看似公平的游戏却把规则定的自己总有必胜策略…想到东方夜神雪里面那个取硬币小游戏…轮流取1~3枚,取走最后一枚的人输…可是起始的硬币数量并不是随机的…而是4k+1…太囧了…玩了好几盘才发现原来这游戏是必输的…
回到这里…这次是类似孔明棋的小游戏…每次可以选一个棋子往4个方向之一跳,但是必须跳过别的棋子并且最终落在某个空格上,中间可以跳过连续多个棋子,被跳过的棋子都会被拿走…
给定初始棋局,问让铃仙和因幡谁先走可以使得因幡有必胜策略…
一看规模才5*5…想想2^25也不是什么大数字…加上有一句”It’s guaranteed that no more than 61.8% of them are ‘e’s.”…感觉状态会很少…于是直接暴力记录博弈状态…
第一次交忘记处理了选取的棋子是一排棋子中间的某个棋子的情况…改后AC
然后…第魔里沙题有人过…魔炮啊…是个计算几何…求往什么方向射可以打中最多点,魔炮的范围是个顶点为原点的抛物线
抛物线啊…想到每个点有个可被命中的角度范围,也就是魔炮的方向在这个范围内,这个点可以被打中,但是对不同距离的点而言,这个范围的大小是不一样的…
计算了下,二次系数是a的抛物线和半径为r的圆的交点
y坐标是: y=(sqrt(1+4*a*a*r*r)-1)/(2*a)
设上图中P点对应的极角为alpha,那么当魔炮中轴对着[alpha-theta, alpha+theta]区间中任意的极角时,P点就能被打中
这个theta值为: theta=atan(x/y) =atan(sqrt(y/a)/y)=atan(sqrt(1/y*a))
于是问题转换成了,找一个极角,使得它被最多的区间覆盖…而数据规模有3万个点…
脑中第一个闪现的是离散化+线段树…显然太麻烦了…
然后想起以前某些题…比如矩形求并之类的…貌似只要看左右边界判断出入就行…
于是想到了用这个方法就好,将区间变成端点,左端点标记为入,右端点标记为出,然后将所有端点按大小(这里是极角)排序
然后从前往后扫描,遇到标记为入的端点就当前覆盖区间数加一,遇到标记为出的端点就当前覆盖区间数减一,扫描一遍下来,取当前覆盖区间数的最大值…就是所需的答案daze
另外处理下跨边界相邻的情况,就是当区间在[0,2pi]的两边时,就多插入个小于0的那个入端点和大于2pi的那个出端点
然后…有别的事情…于是就看看题目然后不继续做了…
第极题…姬海棠也有啊…貌似是找最安全点…话说游戏里寅丸星的香蕉激光实在是太恶心了…但是这题目里面是射线…而且是曼哈顿距离?…直接傻眼了…点和线的曼哈顿距离?那是什么?怎么求?
第图书题…不动的大图书馆…题目是一共m种元素卡,一共有n种符文,每种元素卡上等概率出现这n种符文中的一种,求m种元素卡各取一张的话,有多少概率可以使得这些卡上的符文至少有l个是相同的…输出成既约分数…
又是组合数类的题目吗…
第咲夜题…时间的操作…哦不…这题是求表达式结果是某个类型的可能性个数?
题目很长呢…
第幽幽子题…赏花会啊…真好呢…
又是做食物…这次是第i天幽幽子会吃掉ai份食物…妖梦每天可以做L份食物,或者花一天时间锻炼自己使得L值增加1…求N天过后剩下的食物最多还有多少份…
这里或者这里是官方解题报告吧…
下面是我灵梦,芙兰,魔里沙题的代码…
tags: ZJU, acm author: ben1222 comments: 2 Comments
有一类题目会因为求出的结果太大而只要求输出对某个数m取余后的结果,而且这个m是比较小的数,比如不超过32位整数…
而这类大数都是可以由较小的数经过某些运算得到的…
于是我整理了一下对付几种运算的方法…包括四则运算,指数,组合数,塔函数的应对方法…
那么就开始吧…慢慢来…
首先是最常识的加减法:
add_mod(a,b,m){
return ((a%m)+(b%m))%m;
}
别小看加法哦…很多用dp解的题目中靠着加法可是能达到很大的数呢…
minus_mod(a,b,m){
return (a-b+m)%m;
}
减法…会遇到吗?
接着是依然很简单的乘法:
multiply_mod(a,b,m){
return ((a%m)*(b%m))%m;
}
这是当m*m不会溢出时可以用的,同时也是通常的情况…
但是如果m*m连long long都会溢出的话…就需要把一个数一位位拆开来做了…
multiply_mod(a,b,m){
if(b==0)return 0;
return (((b&1)?a:0)+(multiply_mod(a,b>>1,m)<<1)%m)%m;
}
然后是除法,但有点限制:
(a/b)%m
特殊条件:m和b互质
前提:a能被b整除
这个有点特殊,意为虽然不知道a是多少,但是已知c,而且c=a%m,用c和b来求(a/b)%m的方法
虽然需要m和b互质,但是不互质的话也是可以做的,因为a也一定是gcd(b,m)的倍数,具体可以看看这里
需要用到扩展欧几里德来求…
至于扩展欧几里德是什么…去Google一下吧…
extend_euclid(a,b,&x0,&y0){
if(b==0){
x0=1;
y0=0;
return [...]
tags: 模板 author: ben1222 comments: 2 Comments
这次的上海赛区…依然悲剧…
唉…就这样结束了…
说起来这次比赛办的…怎么说…感觉不太好…
题目…有点难…应该说真正难的题目不多…但是代码量和思考量都比较大…
最后是2题…银…
某解题报告
A: 超立方体…实际上只是一个图,每步可以交换一条边上两个点的状态,不过两个点状态相同的话是不允许交换的,给定一个状态,要求最少多少步弄成1~8是关,9~16是开的状态,如果超过3步直接输出more…
数据量比较大但是状态非常少,简单的预处理出从目标状态bfs出3步内状态就行了
B: 呃…简单来说就是给出递推公式f(n)=f(n-1)*f(n-2),f(1)=a,f(2)=b,求f(n)%p的值,n规模10^9,a,b,p规模10^6…
推一下就得到了f(n)=a^(Fibonacci(n-2))*b^(Fibonacci(n-1))%p…但是接下来怎么求呢…于是想到循环节…
找a^k%p和b^k%p的循环起始位置和循环节长度,然后把Fibonacci的转移矩阵拿去二分求…取余的地方改成:如果大于循环起始位置,就减去该值,对循环节长度取余,然后加上该值
求完就二分求a^x1*b^x2%p…因为不是很有把握…ac的时候兴奋了一把…
C: 判两个被压缩过的字符串是否相等,如果不等,输出第一个不等的位置…压缩方式类似汇编里面那个DUP…字符串原始长度是高精度级别…没想法…
D: 两部分,第一步是求满足x^q%p=a的所有小于p的x值,其中p是10^9级别,q很小,规模才10,第二步是计算2000.01.01 00:00:00经过x秒后的时间,要考虑闰年和闰秒…
第二步不难…可惜第一步实在没想法…
E: 模拟俄罗斯方块…求最后得分和各列最高位置…当我看到游戏区域的宽度规模有3万时…就放弃了这题…
F: 土地分成n列m行格子,有n种花,初始给出每个格子的花的种类满足:每行每列都没有相同的花…现在要增加一行,依然满足上述条件,求出所有方案中字典序第k大的一种种花方案…规模200…
这个…二分图的字典序第k大完美匹配…我没有思路…answeror试了一次n^4.x级别的…结果tle了…然后就放弃掉了…
G: 第一句写着:如果谁做出这道题,结束后将会得到两幅纸牌作为赠品,七页纸的描述啊…超级模拟题…吧…
H: 一堆四面体,每个四面体有一个顶点是(0,0,0)…然后…选出最多的互不相交(不包括(0,0,0))的四面体…规模40…判四面体相交没有准备模板也不好想…所以就没管…
I: 给定一堆点,他们必定在两条线段上,点间距离作为权值,计算最小生成树…规模2万…由于点分布的特殊性…所以可以舍去许多边…
虽然猜想了一种构图:每个点只和前后两点以及在另一线段的垂足附近的点相连…可是wa到死…当看到解题报告也是这么做的时候崩溃了…幸好当时这道题打印了代码…重新读一遍的时候终于发现了问题所在…我算垂足的时候…居然算到点所在线段而不是另一条线段上去了…囧…太可悲了…
J: 劲乐团?…7个键,乐谱有两种,一种是点,一种是线,点的只要按一下就能得1分,线的在起点按下会得一分,如果直到终点才松开的话又能得一分,如果中途松开就得不到后面那一分…然后有些键是不能同时按的,否则那个时间点上的得分都算0…给定乐谱,规模1000,以及各组会产生冲突的按键,求最多能得几分…
这题有很多人过…可是我们却卡住了…最后一小时answeror突然发现原来就是个dp…然后我来敲…结果敲的时候脑子里就像在口袋里放久了的一堆耳机线…可谓混乱至极…敲完了还出不了样例…最后5分钟好不容易出了样例…结果wa了…当发现一个错误并改正后…发现又出不了样例了…囧…然后…没时间了…又一悲剧…
下面是牢骚(?)
tags: acm author: ben1222 comments: 1 Comment
恩…刚结束的宁波赛区比赛…
话说比赛结束时就感到我们要悲剧了…
不过还好结果没有坏到预期的地步…
首先不得不说的是…纪念品…杯具等…
还有自助晚宴真是豪华啊…各种肉和水产品…每样拿一个都够撑死我了…
当然还有点心,汤,水果,饮料,还有米饭…
看着别人拿了一堆…真佩服他们的胃…
我拿的东西还没超出盘子凹陷的部分…就吃饱了…胃口真小…
比赛结果…悲剧的是我们队只做出4题…并且后2小时貌似没有出题…而且还不是没有思路…有1~2题应该能出的…
不算太坏的是…ICPC排名踩在银牌尾巴上…并且是唯一4题拿银的…
这次比赛深刻的感受到…水题做太多了…不过话说我最近也没怎么做题…
如果把做水题的时间去做别的题的话…可是读了题发现自己会做…就会不甘心放在那里…而是花上几分钟或十几分钟去A掉…这种冲动…
闭幕的时候裁判简单说了下各道题的类型…
下面是详细内容
tags: acm author: ben1222 comments: No Comments