数学 - Page 8 - hzwer.com

「codechef」January Challenge 2015
CHEFSTON[crayon-67687f5c1fd08211378305/]GCDQgcd满足区间加法TAT，所以维护前缀和后缀和就好了[crayon-67687f5c1fd12419375549/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-67687f5c1fd18505391501/]ONEKING按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。剩下的线段同理[crayon-67687f5c1fd1c767417116/]CLPERM答案根据第一个不能合成的数奇偶性得...
02015年1月12日6,293模拟,贪心,构造,数学,快速幂,随机化,容斥原理,最大公约数与最小公倍数

「点分治练习」[hdu4812] multik
「问题描述」给定一棵n个点的树,每个点有权值Vi问是否存在一条路径使得路径上所有点的权值乘积mod(10^6+3)为K输出路径的首尾标号,若有多解,输出字典序最小的解「输入格式」第一行两个数n,K第二行n个数,表示vi接下来n-1行每行两个数x,y表示一条边「输出格式」输出两个数a,b(a<b),无解输出”Nosolution”(不含引号)。「样例输入」5602523312132425「样例输出」34「数据规模与约定」对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2...
62015年1月12日6,302点分治,乘法逆元
「CODEVS1515」跳
题目描述Description邪教喜欢在各种各样空间内跳。现在，邪教来到了一个二维平面。在这个平面内，如果邪教当前跳到了(x,y)，那么他下一步可以选择跳到以下4个点：(x-1,y),(x+1,y),(x,y-1),(x,y+1)。而每当邪教到达一个点，他需要耗费一些体力，假设到达(x,y)需要耗费的体力用C(x,y)表示。对于C(x,y)，有以下几个性质：1、若x=0或者y=0，则C(x,y)=1。2、若x>0且y>0，则C(x,y)=C(x,y-1)+C(x-1,y)。3、若x<0且y<0，...
72015年1月9日4,075贪心,快速幂,排列组合,乘法逆元
「codechef」December Challenge 2014
「codechefCAPPLE」ChefandAppleTrees其实我想练习打字，点开codechef随便做。。。后来发现这是在challenge，后来补了俩题[crayon-67687f5c216f2657282972/]「codechefXORSUB」XORwithSubset求线性基，裸题[crayon-67687f5c216fb540389042/]「codechefSANSKAR」Alok-nathandHisSanskars从大到小排序后优先用大的合成随便搜索一下TAT这样过了codechef但是似乎会被构造卡掉144151017161211020171945...
02015年1月9日3,073模拟,深度搜索,高斯消元
「BZOJ2460」[BJ2011] 元素
Description 相传，在远古时期，位于西方大陆的MagicLand上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消”。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后...
12015年1月8日5,506贪心,高斯消元
「CF500D」New Year Santa Network
NewYeariscominginTreeWorld!Inthisworld,asthenameimplies,therearencitiesconnectedbyn - 1roads,andforanytwodistinctcitiestherealwaysexistsapathbetweenthem.Thecitiesarenumberedbyintegersfrom1ton,andtheroadsarenumberedbyintegersfrom1ton - 1.Let'sdefined(u, v)astotallengthofroadsonthepathbetweencityuandcityv.Asanannualevent,peopleinTreeWorldrepairsexactlyoneroadperyear.Asaresult,theleng...
02015年1月4日3,730树形动规,排列组合
「BZOJ1965」[Ahoi2005] SHUFFLE 洗牌
\[x*(2^m)\equivl(mod~n+1)\]x在modn+1下逆元是n/2+1所以移项得\[x\equiv(n/2+1)^m*l(mod~n+1)\][crayon-67687f5c22727163262883/]
12014年12月30日4,159快速幂,乘法逆元
「BZOJ2242」[SDOI2011] 计算器
Description你被要求设计一个计算器完成以下三项任务：1、给定y,z,p,计算Y^ZModP的值；2、给定y,z,p，计算满足xy≡Z(modP)的最小非负整数；3、给定y,z,p，计算满足Y^x≡Z(modP)的最小非负整数。Input 输入包含多组数据。第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。以下行每行包含三个正整数y,z,p，描述一个询问。Output对于每个询问，输出一行答案。对于询问...
62014年12月29日7,549BSGS
「POJ1284」Primitive Roots
DescriptionWesaythatintegerx,0<x<p,isaprimitiverootmodulooddprimepifandonlyiftheset{(ximodp)|1<=i<=p-1}isequalto{1,...,p-1}.Forexample,theconsecutivepowersof3modulo7are3,2,6,4,5,1,andthus3isaprimitiverootmodulo7.Writeaprogramwhichgivenanyoddprime3<=p<65536outputsthenumberofprimitiverootsmodulop.InputEachlineoftheinputcontainsanoddprimenumbersp.Inputisterminatedbytheend-of-...
02014年12月29日4,229筛法,欧拉函数
「BZOJ2186」[SDOI2008] 沙拉公主的困惑
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。Input第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R...
62014年12月28日8,884筛法,欧拉函数,乘法逆元
「codechefTASTRMAT」String Matching
其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。你们就坑我吧设L=n-m对于B的第1个字符，其匹配的是A的一个区间1到1+L若其与A[1]不同，则hash值增加100001^m与A[1+K]不同，则hash值增加100001^(n-K)用数据结构支持查询1到1+L对hash值的贡献即第K位与B的第1个字符不同则hash值增加100001^(n-K)，相同增加0用个线段树or树状数组（实际上前缀和就行）接着考虑对于B的第2个字符，其匹配的是A的一个区间2到2+L若...
02014年12月28日2,930线段树,乘法逆元
「CF498B」Name That Tune
ItturnsoutthatyouareagreatfanofrockbandAC/PE.Peterlearnedthatandstartedthefollowinggame:heplaysthefirstsongofthelistofnsongsofthegroup,andyouhavetofindoutthenameofthesong.Afteryoutellthesongname,Peterimmediatelyplaysthefollowingsonginorder,andsoon.Thei-thsongofAC/PEhasitsrecognizabilitypi.Thismeansthatifthesonghasnotyetbeenrecognizedbyyou,youlistentoitforexactlyonemoresecondandwithpr...
12014年12月25日3,625递推与动规,概率与期望