快速幂 - Page 2

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

「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日3,832贪心,快速幂,排列组合,乘法逆元
「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-6623ab14355bc397241236/]
12014年12月30日3,953快速幂,乘法逆元
「BZOJ2751」[HAOI2012] 容易题(easy)
Description为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和mod1000000007的值，是不是很简单呢？呵呵！Input第一行三个整数n,m,k分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。接下来k行，每行...
12014年12月9日5,124快速幂
「NOIP模拟赛」calc
题目说明给三个正整数n，m和p，求(n^1+...n^m)modp。输入格式一行，三个整数n，m和p。输出格式输出答案。样例SampleInput225SampleOutput1数据范围n,p<=10^8m<=10^17相关信息文件名:calc.pas/c/cpp输入文件:calc.in输出文件:calc.out时限:1s空间限制:64MB题解暴力直接快速幂正解应该是矩阵乘法然后我作死试图用数论。。。逆元没学好根据等比数列求和公式得到（省略）/（n-1）modp发现n-1和p可能不互质，然后（省略）/（...
02014年11月6日3,609快速幂,乘法逆元
「BZOJ1951」[SDOI2010] 古代猪文
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。猪王国虽然不大，但是土地肥沃，屋舍俨然...
22014年9月14日8,198快速幂,排列组合,模线性方程组,扩展欧几里得算法
「CF464C」Substitutes in Number
AndrewandEugeneareplayingagame.Initially,Andrewhasstrings,consistingofdigits.EugenesendsAndrewmultiplequeriesoftype"di → ti",thatmeans"replacealldigitsdiinstringswithsubstringsequaltoti".Forexample,ifs = 123123,thenquery"2 → 00"transformssto10031003,andquery"3 → "("replace3byanemptystring")transformsittos = 1212.AfterallthequeriesEugeneasksAndrewtofindtheremainderafterdivisi...
02014年9月8日3,618快速幂,离线处理
「NOIP模拟赛」果实计数
题目描述：淘淘家有棵奇怪的苹果树，这棵树共有n+1层，标号为0~n。这棵树第0层只有一个节点，为根节点。已知这棵树为b叉树，且保证是一颗满b叉树。如图为一颗满3叉树。现在，该树第n层的每个节点上都结出了一个苹果，淘淘想知道共结了多少苹果。由于数量可能很大，答案要求输出modk后的结果。输入描述：给出第1层的节点数b和层数n和k.输出描述：输出苹果数modk后的结果。样例输入：2109样例输出：7数据范围：30%的数据保证：b<=...
02014年8月2日2,613快速幂
「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,088快速幂
NOI2002Robot
DescriptionInputOutputSampleInput3213251SampleOutput8675HINT90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。题解为何我觉得这题十分恶心f[i][0]表示前i个因数（不含2）的乘积m和它的老师中政客的独立数之和（包括自己）f[i][1]表示前i个因数（不含2）的乘积m和它的老师中军人的独立数之和（包括自己）[crayon-6623ab146c1a430095...
12014年6月1日3,285快速幂,欧拉函数
「JoyOI1118 – 1119」a^b1 – 2
a^b描述Description求a^b由于结果可能很大，我们现在只需要知道这个值mod 1012就可以了（为什么是1012？我的生日）a<1000000b<1000000输入格式InputFormat第一行两个数 a b输出格式OutputFormat一行，就是mod 1012的值样例输入SampleInput22样例输出SampleOutput4代码快速幂[crayon-6623ab146d1c5330439782/]1119有多组数据[crayon-6623ab146d1ce252583663/] ...
02014年1月27日2,520快速幂
「CODEVS1851」越狱
题目描述 Description监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱输入描述 InputDescription输入两个整数M，N.1<=M<=10^8,1<=N<=10^12输出描述 OutputDescription可能越狱的状态数，模100003取余样例输入 SampleInput23样例输出 SampleOutput6数据范围及提示 Dat...
02014年1月5日3,541快速幂