乘法逆元 - hzwer.com

「FJ2015集训」热身题
「问题描述」定义F：F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)(n>=3)定义p：p(i)=a1*F(1)^i+a2*F(2)^i+…+ak*F(k)^i其中k和a1…ak为常数。现在已知k,p(1),p(2),…,p(k)，求p(k+1)。为了避免高精度，所有运算都模掉M。保证F(1),…,F(n)在模质数M下两两不同，保证有唯一解。「输入格式」第一行，两个整数k,M。第二行，p(1),p(2),...,p(k)模M。「输出格式」输出p(k+1)模M。「样例输入1」310151129「样例输出1」83「样例输...
12015年7月12日4,955快速幂,高斯消元,乘法逆元

「codechef」April Challenge 2015
BROKPHON模拟[crayon-673fa5cead4df075382758/]CHEFLCM所有约数和[crayon-673fa5cead4e9114948443/]PIANO1暴力TT[crayon-673fa5cead4ed003626891/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-673fa5cead4f1097328553/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日4,874模拟,递推与动规,ST表,并查集,排列组合,乘法逆元
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日5,813线段树,筛法,欧拉函数,乘法逆元
「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,854乘法逆元
「点分治练习」[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,277点分治,乘法逆元
「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,054贪心,快速幂,排列组合,乘法逆元
「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-673fa5ceaf598865709504/]
12014年12月30日4,121快速幂,乘法逆元
「BZOJ2186」[SDOI2008] 沙拉公主的困惑
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。Input第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R...
62014年12月28日8,862筛法,欧拉函数,乘法逆元
「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,913线段树,乘法逆元
「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,796快速幂,乘法逆元
「BZOJ3398」[Usaco2009 Feb] Bullcow 牡牛和牝牛
Description 约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛．牛们要站成一排．但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛．请计算一共有多少种排队的方法．所有牡牛可以看成是相同的，所有牝牛也一样．Input 一行，输入两个整数N和K.Output 一个整数，表示排队的方法数．SampleInput42Sampl...
02014年10月1日5,774排列组合,乘法逆元
「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日6,341排列组合,乘法逆元,容斥原理