数学 - Page 12 - hzwer.com

「BZOJ3629」[JLOI2014] 聪明的燕姿
Description阴天傍晚车窗外未来有一个人在等待向左向右向前看爱要拐几个弯才来我遇见谁会有怎样的对白我等的人他在多远的未来我听见风来自地铁和人海我排着队拿着爱的号码牌城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字S，那么自己等的人手上的号码牌数字的所有正约数...
12014年8月14日5,590深度搜索,筛法

「NOIP模拟赛」果实计数
题目描述：淘淘家有棵奇怪的苹果树，这棵树共有n+1层，标号为0~n。这棵树第0层只有一个节点，为根节点。已知这棵树为b叉树，且保证是一颗满b叉树。如图为一颗满3叉树。现在，该树第n层的每个节点上都结出了一个苹果，淘淘想知道共结了多少苹果。由于数量可能很大，答案要求输出modk后的结果。输入描述：给出第1层的节点数b和层数n和k.输出描述：输出苹果数modk后的结果。样例输入：2109样例输出：7数据范围：30%的数据保证：b<=...
02014年8月2日2,637快速幂
「CF453A」Little Pony and Expected Maximum
TwilightSparklewasplayingLudowithherfriendsRainbowDash,AppleJackandFlutterShy.Butshekeptlosing.Havingreturnedtothecastle,TwilightSparklebecameinterestedinthedicethatwereusedinthegame.Thedicehas m faces:thefirstfaceofthedicecontainsadot,thesecondonecontainstwodots,andsoon,the m-thfacecontains m dots.TwilightSparkleissurethatwhenthediceistossed,eachfaceappearswithprobability .A...
02014年8月2日3,496概率与期望
「BZOJ1697」[Usaco2007 Feb] Cow Sorting牛排序
Description农夫JOHN准备把他的N（1<=N<=10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。请帮JOHN计算把所有牛排好序的最短时间。Input第1行：一个数，N。...
32014年7月29日5,247置换
「CF451E」Devu and Flowers
Devuwantstodecoratehisgardenwithflowers.Hehaspurchased n boxes,wherethe i-thboxcontains fi flowers.Allflowersinasingleboxareofthesamecolor(hencetheyareindistinguishable).Also,notwoboxeshaveflowersofthesamecolor.NowDevuwantstoselect exactly s flowersfromtheboxestodecoratehisgarden.Devuwouldliketoknow,inhowmanydifferentwayscanheselecttheflowersfromeachbox?Sincethisnumbermaybeverylarg...
12014年7月25日5,966排列组合,乘法逆元,容斥原理
「CF451A」Game With Sticks
AfterwinninggoldandsilverinIOI2014,AkshatandMalvikawanttohavesomefun.Nowtheyareplayingagameonagridmadeof nhorizontaland m verticalsticks.An intersectionpoint isanypointonthegridwhichisformedbytheintersectionofonehorizontalstickandoneverticalstick.Inthegridshownbelow, n = 3 and m = 3.Thereare n + m = 6 sticksintotal(horizontalsticksareshowninredandverticalsticksareshowni...
02014年7月25日3,179博弈论
「fj夏令营」营销策略
「题目描述」W记的儿童套餐会赠送一份小玩具，赠送的小玩具共有n种。小朋友买了m份儿童套餐，求收集齐n种小玩具的概率。假设每份儿童套餐赠送的小玩具的种类是等概率随机的。「输入格式」从pattern.in中输入数据一行，两个整数n，m。「输出格式」输出到pattern.out中一个实数表示收集齐小玩具的概率，保留4位小数。「样例输入」23「样例输出」0.7500「数据规模与约定」对于10%的数据保证：n=1对于30%的数据保证：n≤2对于60%的数据...
02014年7月20日3,133递推与动规,概率与期望
「fj夏令营」求和
「题目描述」作为本场考试最水的一题,给定n,k和m,请你计算:(1^k+2^k+3^k+...+n^k)modm「输入格式」从sum.in中输入数据一行,三个整数,n,k,m「输出格式」输出到sum.out中一行,(1k+2k+3k+...+nk)modm「样例输入」4398「样例输出」2「数据规模与约定」数据规模1：n≤2^63−1,k=1,m≤2^31−12-3：n≤10^6,k≤100,m≤10^74-5：n≤10^8,k≤10^7,m≤3∗10^76-10：n≤2^63−1,k≤2^63−1,m≤1.5∗10^6题解本题时限为2s。。。事实上标程极限数...
02014年7月20日3,113快速幂
「NOIP模拟赛」合唱队形
「问题描述」学校要进行合唱比赛了，于是班主任小刘准备给大家排个队形。他首先尝试排成m1行，发现最后多出来a1个同学；接着他尝试排成m2行，发现最后多出来a2个同学，……，他尝试了n种排队方案，但每次都不能让同学们正好排成mi行。于是小刘寻求同事小明的帮助，以便给同学们排好队形。但小刘来去太匆忙，忘记告诉小明他们班有多少人了。没办法，现在只能根据上述信息求个满足要求的最小的数字来作为人数了。虽然小明年轻时是理科...
02014年7月10日3,908扩展欧几里得算法
「NOIP模拟赛」hash函数
「问题描述」明明觉得hash是个好算法，代码短、效率高。某天，他碰到了一个求正方形个数的问题，于是很淡定地枚举对角线，然后用hash判存在，妥妥的搞定，但是提交后却wa了几个点。仔细观察其hash函数为：h=x*y+x+y。为了让明明知道这个函数存在什么问题，对于给出一个h值，请你来告诉他有多少对(x，y)满足上述式子(max(x,y)≤h；h，x，y都为非负整数)?「输入格式」多组测试数据，第一行为测试点的个数T，接下来每一行一个整数h，...
02014年7月10日2,819筛法
「CF442B」Andrey and Problem
Andreyneedsonemoreproblemtoconductaprogrammingcontest.Hehas n friendswhoarealwayswillingtohelp.Hecanasksomeofthemtocomeupwithacontestproblem.Andreyknowsonevalueforeachofhisfiends—theprobabilitythatthisfriendwillcomeupwithaproblemifAndreyaskshim.HelpAndreychoosepeopletoask.Asheneedsonlyoneproblem,Andreyisgoingtobereallyupsetifnoonecomesupwithaproblemorifhegetsmorethanoneproblemfromhisfr...
02014年6月20日3,002概率与期望
「BZOJ2705」[SDOI2012] Longge的问题
DescriptionLongge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i,N)(1<=i<=N)。Input一个整数，为N。Output一个整数，为所求的答案。SampleInput6SampleOutput15HINT「数据范围」对于60%的数据，0<N<=2^16。对于100%的数据，0<N<=2^32。题解题目中要求出∑gcd(i,N)(1<=i<=N)。枚举n的约数k，令s(k)为满足gcd(m,n)=k,(1<...
02014年6月15日6,302欧拉函数