• 等级
  • 11646 访问
  • 178 原创
  • 0 转发
  • 34989 排名
  • 21 评论
  • 6 获赞

洛谷 P-3626(实数下线性基 or 高斯消元)

https://www.luogu.org/problemnew/show/P3265题意:有n个m项的向量,每个向量还有个花费,问最少多少花费能组合出最多的向量思路:高斯消元这道题,一眼就可以知道高斯消元可写,我们把每个向量的每一项合在一起写成一个矩阵[a1.v1a1.v2a1.v3...a1.vma2.a1a2.v2a2.v3...a2.vma3.a1a3.v2a3.v3...a3...

2019-04-23 11:41:50

阶梯Nim

阶梯Nim类似题目:nnn个位置,每个位置有aia_iai​个石子,两个人轮流操作,把第iii个位置的石子挪到i−1i-1i−1个位置。谁不能在操作,谁为输。结论:求奇数位上的石子数的异或和洛谷P3480题目大意:n对石子,每堆石子个个数不能少于前一堆石子,两个人轮流拿石子,谁不能拿为输。思路:因为每堆石子的个数不能少于前一堆石子。那么如果我拿走第iii堆的石子,那么第i+1i...

2019-04-14 14:02:26

暂时性的模板

KMPints[maxn],t[maxn],Next[maxn];//ss大tt小stringtt,ss;inttlen,slen;voidgetNext(){//自己跟自己比较,求的是子串的最大前缀和最大后缀的长度intj,k;j=0;k=-1;Next[0]=-1;while(j<tlen)//j是tt...

2019-04-09 10:34:33

洛谷:P3747 相逢是问候(线段树+指数循环节)

https://www.luogu.org/problemnew/show/P3747题目大意:Informatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组,这个数组的下标为从1到n的正整数。一共有m个操作,可以分为两种:0lr表示将第l个到第r个数(al,al+1,...aral,al+1,.....

2019-04-02 20:30:19

洛谷 P3726 抛硬币 (拓展卢卡斯+数论)

https://www.luogu.org/problemnew/show/P3726题意:A扔a个硬币,B仍b个硬币(a≥b),求A硬币正面朝上的数量大于B硬币朝上的数量的种类数A扔a个硬币,B仍b个硬币(a\geqb),求A硬币正面朝上的数量大于B硬币朝上的数量的种类数A扔a个硬币,B仍b个硬币(a≥b),求A硬币正面朝上的数量大于B硬币朝上的数量的种类数思路:我们可以把A和B的硬币...

2019-03-29 23:10:06

洛谷 P3301 [SDOI2013]方程(容斥+数论+扩展卢卡斯)

https://www.luogu.org/problemnew/show/P3301题意:求X1+X2+X3+...+Xn=MX_1+X_2+X_3+...+X_n=MX1​+X2​+X3​+...+Xn​=M的所有正整数解的种类数并且有如下要求在Xi≤Ai(1≤i≤n1)Xi≥Ai(n1+1≤i≤n1+n2)X_i\leqA_i(1\leqi\leqn_1)\\X_i\geq...

2019-03-25 21:40:09

洛谷P2480 [SDOI2010]古代猪文(指数循环节+扩展卢卡斯)

https://www.luogu.org/problemnew/show/P2480题意:求G∑d∣NCNd(mod  999911659)求G^{\sum\limits_{d|N}C_{N}^{d}}(\mod999911659)求Gd∣N∑​CNd​(mod999911659)思路:因为∑d∣NCNd的值会非常巨大,所以我们可...

2019-03-23 20:20:41

洛谷 P4884 多少个1?(BSGS)

https://www.luogu.org/problemnew/show/P4884题目大意:求:111…1111modm=K思路:我们把前面的111…111乘9+1就变成10n10^n10n原式=10n≡9⋅k+1(mod  m)10^n\equiv9\cdotk+1(\modm)10n≡9⋅k+1(modm)这...

2019-03-19 11:46:15

扩展中国剩余定理

#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintMod=1e9+7;constintmaxn=1e6+5;constdoubleeps=0.00000001;constintINF=0x3f3f3f3f;LLn;LLM[maxn...

2019-03-15 23:15:07

扩展卢卡斯

卢卡斯定理:Cnmmod  pC_n^m\modpCnm​modpp为素数拓展卢卡斯:Cnmmod  pC_n^m\modpCnm​modpp不是素数根据中国剩余定理:p=∏i=1kpiaip=\prod\limits_{i=1}^{k}p_i^{a_i}p=i=1∏...

2019-03-13 22:40:06

拓展欧几里得(模板)

LLextend_gcd(LLa,LLb,LL&x,LL&y){if(!b){x=1;y=0;returna;}LLd=extend_gcd(b,a%b,x,y);LLt=x;x=y;y=t-(a/b)...

2019-03-11 22:17:25

洛谷 P3986 斐波那契数列 (拓展欧几里得)

https://www.luogu.org/problemnew/show/P3986题目:f(1)=a,f(2)=b,...,f(n)=f(n−1)+f(n−2)f(1)=a,f(2)=b,...,f(n)=f(n-1)+f(n-2)f(1)=a,f(2)=b,...,f(n)=f(n−1)+f(n−2)求斐波那契数列中,第一项是aaa,第二项是bbb,问数列中存在kkk...

2019-03-11 16:07:42

中国剩余定理优化RSA(2018 CCPC-Final K)

中国剩余定理:{x≡a1(mod  m1)x≡a2(mod  m2)...x≡an(mod  mn)\begin{cases}x\equiva_1(\modm_1)\\x\equiv

2019-03-05 21:25:03

数论小结论(持续更新)

∑i=1n[gcd⁡(i,n)==1]i\sum\limits_{i=1}^{n}[\gcd(i,n)==1]ii=1∑n​[gcd(i,n)==1]i在[1,n]中,与n互质的数的和=φ(n)∗n+[n==1]2=\frac{\varphi(n)*n+[n==1]}{2}=2φ(n)∗n+[n==1]​

2019-03-03 19:16:50

51Nod 最大公因数之和+最小公倍数之和(杜教筛)

1238最小公倍数之和http://www.51nod.com/Challenge/Problem.html#!#problemId=12381237最大公因数之和http://www.51nod.com/Challenge/Problem.html#!#problemId=1237先来说最大公因数之和:1237最大公因数之和∑i=1n∑j=1ngcd⁡(i,j)\sum\lim...

2019-02-22 17:08:16

[SDOI2015]约数个数和 (莫比乌斯反演)

https://www.lydsy.com/JudgeOnline/problem.php?id=3994题意:设d(x)为x的约数个数,给定N、M,求Σi=1nΣj=1md(ij){\Sigma_{i=1}^n\Sigma_{j=1}^md(ij)}Σi=1n​Σj=1m​d(ij)思路:首先我们先了解一个公式:d(ij)=Σx∣iΣy∣j[gcd(x,y)==1]d(ij)=\S...

2019-02-19 10:51:00

线性筛莫比乌斯函数&欧拉函数(模板)

boolvis[Maxn];intmu[Maxn],prim[Maxn];voidMoblus(){mu[1]=1;inttot=0;for(inti=2;i<=Maxn;i++){if(!vis[i]){prim[tot++]=i;mu[...

2019-02-18 11:41:57

CCPC-Wannafly Winter Camp Day4 (div2)(dp)

题目描述wlswls有一个整数nn,他想请你算一下有多少1…n1…n的排列(permutation)满足:对于所有的i(2\lei\len)i(2≤i≤n),若ii为奇数,则a[i-1]<a[i]a[i−1]<a[i],否则a[i-1]>a[i]a[i−1]>a[i]。请输出答案mod1e9+7。输入描述一行一个整数nn。1\len...

2019-01-25 23:48:24

CF:Tree with Maximum Cost

http://codeforces.com/contest/1092/problem/F题目:有一棵树,树的每个节点都有其权值问一个树上以某个点为树的根节点,其他点到根节点的距离乘上权值最大是多少思路:可以运用树状dp解决:假设suma[x]代表x的子树的权值大小,dp[x]代表x的子树到x的距离乘上权值的大小,那么x的父节点y的suma[y]就为suma[x]+a[y],而d...

2019-01-06 19:49:05

CF:New Year and the Sphere Transmission

http://codeforces.com/contest/1091/problem/C分析:我们以n=16分析,发现:1,3,5,7,9,11,13,15的值相同:都为(1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16)2,6,10,14的值相同,都为(1+3+5+7+9+11+13+15)4,12的值相同,都为(1+5+9+13)8的值,都为(1+9)...

2019-01-01 17:49:07

henu_jizhideqingwa

关注
奖章
  • 持之以恒