数学 - Page 7 - hzwer.com

「fjWC2015」世界树
「题目描述」奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值+1，如果一个节点没有子树，其奥术力量为1，这些节点被称为“源”。世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对...
02015年2月4日4,457二分法,高精度,矩阵乘法

「fjWC2015」圣诞树
「题目描述」用m种颜色的彩球装点n层的圣诞树。圣诞树的第i层恰由l[i]个彩球串成一行，且同一层内的相邻彩球颜色不同，同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案，答案对p取模。只要任一位置上的彩球颜色不同，就算作不同的方案。「输入格式」第一行三个整数n,m,p，表示圣诞树的层数、彩球的颜色数和取模的数。接下来一行包含n个整数，表示l[i]。「输出格式」一个整数表示答案。「样例输入」321000312「样例输出」...
02015年2月4日3,325递推与动规,排列组合
「fjWC2015」Galaxy
「题目描述」小X进入了平行宇宙,想在某个平行宇宙开始一段生活。平行宇宙之间用长度为N的仅含有A、B、C、D四个字母的序列标识。每一个由A,B,C，D组成的长度为N的序列标识着不同的平行宇宙。有趣的是，不同的宇宙对应着小X的不同人生，在某些宇宙中，小X的人生过得并不愉快。小X得到了M个特征碎片，特征碎片都为长度小于10的由A,B,C,D构成的序列。如果某个平行宇宙的标识序列包含某个特征碎片（即特征碎片为宇宙...
02015年2月3日4,435AC自动机,矩阵乘法
「CF398B」Painting The Wall
Useraintadecidedtopaintawall.Thewallconsistsofn2tiles,thatarearrangedinann × ntable.Sometilesarepainted,andtheothersarenot.Ashewantstopaintitbeautifully,hewillfollowtherulesbelow.Firstlyuseraintalooksatthewall.Ifthereisatleastonepaintedcelloneachrowandatleastonepaintedcelloneachcolumn,hestopscoloring.Otherwise,hegoestostep2.Useraintachooseanytileonthewallwithuniformprobability.Ifthetil...
02015年2月1日3,869递推与动规,概率与期望
「BZOJ1998」[HNOI2010] Fsk物品调度
Description现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p)modm。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi)modn，xi,yi是为了...
02015年1月31日4,302置换,并查集
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日5,637线段树,筛法,欧拉函数,乘法逆元
「CF364D」Ghd
JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...
02015年1月20日3,675随机化,最大公约数与最小公倍数
「POJ3696」The Luckiest number
DescriptionChinesepeoplethinkof'8'astheluckydigit.Bobalsolikesdigit'8'.Moreover,BobhashisownluckynumberL.NowhewantstoconstructhisluckiestnumberwhichistheminimumamongallpositiveintegersthatareamultipleofLandconsistofonlydigit'8'.InputTheinputconsistsofmultipletestcases.EachtestcasecontainsexactlyonelinecontainingL(1≤L≤2,000,000,000).Thelasttestcaseisfollowedbyalinecontainingazero.O...
02015年1月16日4,465筛法,快速幂,欧拉函数
「BZOJ3529」[SDOI2014] 数表
Description 有一张N×m的数表，其第i行第j列（1<=i<=礼，1<=j<=m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。Input 输入包含多组数据。输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a|<=10^9)描述一组数据。Output 对每组数据，输出一行一个整数，表示答案模2^31的值。SampleInput244310105SampleOutput20148HIN...
22015年1月13日7,102莫比乌斯反演
「BZOJ2820」YY的GCD
Description神犇YY虐完数论后给傻×kAc出了一题给定N,M,求1<=x<=N,1<=y<=M且gcd(x,y)为质数的(x,y)有多少对kAc这种傻×必然不会了，于是向你来请教……多组输入Input第一行一个整数T表述数据组数接下来T行，每行两个正整数，表示N,MOutputT行，每行一个整数表示第i组数据的结果SampleInput21010100100SampleOutput302791HINTT=10000N,M<=10000000Source 假定n<m\[\sum_{isprime(p)...
62015年1月12日9,331莫比乌斯反演
「BZOJ2956」模积和
Description　求∑∑((nmodi)*(mmodj))其中1<=i<=n,1<=j<=m,i≠j。Input第一行两个数n,m。Output　　一个整数表示答案mod19940417的值SampleInput34SampleOutput1样例说明答案为(3mod1)*(4mod2)+(3mod1)*(4mod3)+(3mod1)*(4mod4)+(3mod2)*(4mod1)+(3mod2)*(4mod3)+(3mod2)*(4mod4)+(3mod3)*(4mod1)+(3mod3)*(4mod2)+(3mod3)*(4mod4)=1数据规模和约定对于100%的数据n,m<=10^9。题解 \[\sum_{i=1}^{n}\sum_{j...
02015年1月12日5,670乘法逆元
「BZOJ3239」Discrete Logging
DescriptionGivenaprimeP,2<=P<231,anintegerB,2<=B<P,andanintegerN,2<=N<P,computethediscretelogarithmofN,baseB,moduloP.Thatis,findanintegerLsuchthat[crayon-6633af647a983446251307/]InputReadseverallinesofinput,eachcontainingP,B,Nseparatedbyaspace,Outputforeachlineprintthelogarithmonaseparateline.Ifthereareseveral,printthesmallest;ifthereisnone,print"nosolution"...
12015年1月12日4,174BSGS