- 博客(51)
- 收藏
- 关注
RSS订阅
原创 2019太原理工大学第二届程序设计新生赛预赛暨公开赛题解
A - Creeper?按照题目要求，判断输入的字符串是什么，输出对应的字符串即可。读入时需要注意一次读入一行，因为"Awww man."和"Se no!"中间有空格。B - Awww Man第一个观察，最终得分来源于两部分，分别是吃豆子得到的分数和移动所损失的分数。因为要求吃完所有豆子，而每个豆子的得分是固定的，于是这一部分的分数是固定的，即所有豆子的分数之和。而对于第二部分——移...
2019-12-07 17:12:59
1375
1
原创 【归档】关于kuangbin矩阵专题内题目的小结
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。关于kuangbin矩阵专题内题目的小结大致从这几点分类来小结：矩阵运算的简单优化取模要求的些许处理结合矩阵的优化操作各式各样的构造思路常常要求的求和操作1.矩阵运算的简单优化根据结合律，调整矩阵的运算顺序有时可能会有显著优化，这取决于矩阵的形状，如：【HDU-4965】Fast Matrix Calcula...
2020-04-21 19:10:53
238
原创 【归档】关于对a^b % 2^n = b^a % 2^n，当a为奇数时，在范围[1, 2^n]有且仅有一个b使等式成立的证明
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。关于对ab%2n=ba%2na^b \% 2^n = b^a \% 2^nab%2n=ba%2n，当a为奇数时，在范围[1, 2^n]有且仅有一个b使等式成立的证明首先，如果a是奇数，则它不含有因子2，所以b个a相乘必然没有因数2，即aba^bab是个奇数，因此它对一个偶数（这里的2n2^n2n）取模得到的一定是一个奇数，...
2020-04-21 19:10:19
250
原创 【归档】关于奇数的2^t幂被2^(t + 1)取余得1的证明
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。关于奇数的2t2^t2t幂被2(t+1)2^{(t + 1)}2(t+1)取余得1的证明证明：奇数可以表示为(2k + 1)的形式，因此对于(2k+1)2t(2k + 1)^{2^t}(2k+1)2t，我们根据二项式定理有：(2k+1)2t=(2t2t)22tk2t+(2t−12t)22t−1k2t−1+...+(12...
2020-04-21 19:10:03
314
原创 【归档】关于奇数的四次方对16取余（取模）得1的证明
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。关于奇数的四次方对16取余（取模）得1的证明证明：对于一个奇数，它显然可以表示为2k+12k + 12k+1，则根据二项式定理我们有：(2k+1)4=(44)24k4+(34)23k3+(24)22k2+(14)2k+1=16k4+32k3+24k2+8k+1=8k(2k3+4k2+3k+1)+1\begin{alig...
2020-04-21 19:09:47
702
原创 【归档】关于奇数的平方对8取余（取模）得1的证明
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。关于奇数的平方对8取余（取模）得1的证明证明：【注：%表示取余（也叫取模）】对于∀n∈R\forall n \in \mathbb{R}∀n∈R满足n%2=1n \% 2 = 1n%2=1，总∃k∈R\exists k \in \mathbb{R}∃k∈R使得n=2k+1n = 2k + 1n=2k+1。所以有：n...
2020-04-21 19:09:31
969
原创 【归档】证明区间[0, 1]上的所有实值连续函数构成的实向量空间是无限维的
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Show that the real vector space consisting of all real-valued continuous function on the interval [0,1][0, 1][0,1] is infinite-dimensional.证明区间[0,1][0, ...
2020-04-21 19:08:37
2822
原创 【归档】证明F^∞是无限维的
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Prove F∞\mathbb{F}^\inftyF∞ is infinite-dimensional.证明F∞\mathbb{F}^\inftyF∞是无限维的。Solution:设e1=(1,0,0,...)e_1 = (1, 0, 0, ...)e1=(1,0,0,...)，e2=(0,1,0...
2020-04-21 19:07:47
415
原创 【归档】设v1, v2, v3, v4张成V，证明v1 - v2, v2 - v3, v3 - v4, v4也张成V.
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Suppose v1,v2,v3,v4v_1, v_2, v_3, v_4v1,v2,v3,v4 spans VVV.Prove that v1−v2v_1 - v_2v1−v2, v2−v3v_2 - v_3v2−v3, v3−v4v_3 - v_4v3−v4, v4v_4v4 ...
2020-04-21 19:07:21
511
原创 【归档】设Ue是R上的偶函数集合，Uo是R的奇函数集合，证明R^R = Ue与Uo的直和
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Foreword:We use the operator “⊕\oplus⊕” to express “direct sum”.Question:函数f:R→Rf: R \rightarrow Rf:R→R称为偶函数，如果对所有x∈Rx \in Rx∈R均有f(−x)=f(x)f(-x) = f(x)f(−x)=f(x...
2020-04-21 19:06:58
321
原创 【归档】证明或给出反例：如果U1, U2, W是V的子空间，使得U1 + W = U2 + W，则U1 = U2.
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Prove or give a counterexample if U1,U2,WU_1, U_2, WU1,U2,W are esubspaces of VVV such that U1+W=U2+WU_1 + W = U_2 + WU1+W=U2+W, then U1=U2U_1 = U_2U...
2020-04-21 19:06:40
1317
原创 【归档】V的子空间加法运算有单位元吗？哪些子空间有加法逆元？
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Does the operation of addition on the subspaces of VVV have an additive identity? Which subspaces have additive inverses?Solution:Obviously the subspac...
2020-04-21 19:06:13
406
原创 【归档】设U是V的子空间，求U + U
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Suppose that UUU is a subspace of VVV. What is U+UU + UU+U?Solution:U+U=UU + U = UU+U=U.Proof:Take u,v∈Uu, v \in Uu,v∈U. Then every element in U+UU +...
2020-04-21 19:05:50
649
原创 【归档】证明V的三个子空间的并是V的子空间，当且仅当其中一个子空间包含另外两个子空间
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Foreword:标记，目前没有完成这道题，想出证明后会进行完善。Question:Prove that the union of three subspaces of VVV is a subspace of VVV if and only if one of the subspaces of VVV contain...
2020-04-21 19:05:28
1123
1
原创 【归档】证明V的两个子空间的并是V的子空间当且仅当其中一个子空间包含另一个子空间
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Prove that the union of two subspaces of VVV is a subspace of VVV if and only if one of the subspaces of VVV is contained in the other.证明V的两个子空间的并是B的子空间...
2020-04-21 19:05:02
2239
原创 【归档】R到R的周期函数构成的集合是R^R的子空间吗？
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:A function f:R→Rf : \mathbb{R} \rightarrow \mathbb{R}f:R→R is called periodic if there exists a positive number ppp such that f(x)=f(x+p)f(x) = f(x + p)f...
2020-04-21 19:04:40
797
2
原创 【归档】给出R^2的一个非空子集U的例子，使得U对于加法是封闭并且具有加法逆元的，但U不是R^2的子空间
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Give a example of a nonempty subset UUU of R2\mathbb{R}^2R2 such that UUU is closed under addition and under taking additive inverses but U is not a subs...
2020-04-21 19:04:19
780
原创 【归档】给出R^2的一个非空子集U的例子，使得U在标量乘法下是封闭的，但U不是R^2的子空间
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Question:Give an example of a non-empty subset UUU in R2R^2R2 such that UUU is closed under scalar multiplication, but UUU is not a linear subspace of R2R^2R2.So...
2020-04-21 19:03:55
646
原创 【归档】Is {(a, b, c) in F^3 : a^3 = b^3} a subspace of F^3? (the F is R and C)
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。There are two question to be solved:Is {(a,b,c)∈R3:a3=b3(a, b, c) \in \mathbb{R}^3 : a^3 = b^3(a,b,c)∈R3:a3=b3} a subspace of R3\mathbb{R}^3R3?Is {(a,b,c)∈C3:a3...
2020-04-21 19:02:46
165
原创 【归档】Prove that the set of continuous real-valued functions on the interval [0, 1] is a subspace...
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Prove that the set of continuous real-valued functions on the interval [0, 1] is a subspace of R[0,1]R^{[0, 1]}R[0,1]Note Before Proof: 证明一个集合是另外一个集合的子空间，只要证明这个集合...
2020-04-21 19:01:29
299
原创 【归档】What is the square root of i?
Note: 旧的wordpress博客弃用，于是将以前的笔记搬运回来。Solution:Let z=a+biz = a + biz=a+bi be the complex number which is a square root of i, that isz2=(a+bi)2=a2−b2+2abi=iz^{2} = (a + bi)^{2} = a^{2} - b^{2} + 2abi ...
2020-04-21 19:00:56
285
原创 【ICPC模板】组合数学（更新中）
目录Combinatorics（组合数学）康托展开Catalan Number (卡特兰数)通项公式递推关系渐进关系相关问题卡特兰数扩展问题字典序下一个排列STL内置函数范德蒙恒等式推论杨辉恒等式纵向递推式横向递推式对称表达式组合聚合性恒等式推论二项式定理推论多重集合排列数无限多重集有限多重集多重集合组...
2019-05-11 23:11:49
453
原创 【ICPC模板】数论（更新中）
目录Number Theory（数论)扩展欧几里得递归实现递推实现得到(0, mod]之间最小同余整数得到[-mod, 0)之间最大同余整数一元线性同余方程(Linear Congruence Equation)多元一次不定方程（丢番图方程）求解中国剩余定理 (Chinese Remander Theorem, CRT)扩展中国剩余定理 (扩展CRT)...
2019-05-11 22:57:32
622
原创 【ICPC模板】整数快速模幂法（逐次平方法）
LL fastPowMod(LL base, LL p, LL mod) { LL ret = 1; base %= mod; do { if (p & 1) ret = ret * base % mod; base = base * base % mod; } while (p >>= 1); retu...
2019-02-14 15:55:31
214
原创 【ICPC模板】σ因数和函数
含义：σ(n)表示从1到n（包含）的所有n 的因数之和。积性：如果gcd(n, m) = 1，有σ(nm) = σ(n) * σ(m)求值公式：特别地：代码：#include <iostream>using namespace std;const int LIM = 1e7;int prime[LIM];int pos;bool notPri...
2019-02-14 15:54:56
649
原创 【ICPC模板】Miller-Rabin Primality Test(米勒-罗宾随机素性测试)
目录Miller-Rabin Primality Test(米勒-罗宾随机素性测试)静态素数证据表实现（非随机数实现）使用Java大数类判断素数Miller-Rabin Primality Test(米勒-罗宾随机素性测试)静态素数证据表实现（非随机数实现）函数MillerRabin(LL n, LL a)为一次米勒-罗宾测试结果，true表示测试数n有3/4的把握为素数，...
2019-02-14 15:54:46
497
原创 【ICPC模板】最小质因子
最小质因子欧拉线性筛打表实现原理：欧拉线性筛素数法，每个数仅使用其最小素因数筛去。#include <iostream>using namespace std;inline int mini(int a, int b) {return a < b ? a : b;}// 使用欧拉线性筛打最小质因子表const int LIM = 1e6 + 10...
2019-02-14 15:54:36
1994
原创 【ICPC模板】威尔逊定理
若p是素数，则(p – 1)!与p – 1即-1模除p同余。等价的说法是：如果p是素数，则(p – 1)! + 1能被p整除。值得注意的一点是，这个定理的逆命题，即如果对于一个数x，满足条件(x – 1)! + 1可以被x整除，那么x是素数。综上，威尔逊定理给出了判定一个数是否是素数的充要条件，但是因为阶乘函数值的增长非常快，所以使用这个定理来判断一个数的素性会比较低效。...
2019-02-14 15:54:25
412
原创 【ICPC模板】欧拉线性筛素数法
时间复杂度O(n)，生成的素数紧密存放在prime数组中，primepos是它的元素个数。注意：if(!(i % prime[j]))保证每个数仅被其最小的质因数筛去，并且保证j不会超过当前已找出的素数的个数。const int LIM = 1e5 + 10; /* The limit of number to be test */int prime[LIM / 3];b...
2019-02-13 00:02:09
155
原创 【ICPC模板】取模逆元（模反元素）
目录取模逆元（模反元素）互素情形非互素情形取模逆元（模反元素）互素情形抽象代数中的逆元指的是，对于现有的一个集合S以及定义在其上的二元运算R，任意元素与其逆元进行这个运算后可以得到单位元。取模逆元的条件定义在同余式的乘法下，即对于两个整数a和b，如果有：则将b称作a的逆元，同时a也是b的逆元。取模逆元常常用在计算取模表达式时有除法的情况，因为取模运算对除法不...
2019-02-13 00:02:00
2427
原创 【ICPC模板】欧拉函数
目录欧拉函数质因数分解实现（适用于单次求值）打表实现欧拉函数的性质偶数性质 欧拉函数质因数分解实现（适用于单次求值）含义：小于n且与n互素的正整数个数。积性：如果gcd(n, m) = 1，则求值公式：特别地：注意：此实现需要提前调用euler()筛素数函数代码：#include <iostream>#in...
2019-02-13 00:01:49
155
原创 【ICPC模板】卡迈克尔函数
目录卡迈克尔函数卡迈克尔数卡迈克尔函数定义函数λ(n)为：当n为1, 2, 4或奇质数的幂、或奇质数的幂的二倍时，这一函数的函数值等于n的欧拉函数值；当n为2、4之外的2的幂时，这一函数的函数值等于n的欧拉函数值的一半。这一函数满足：欧拉定理与费马小定理都是此式的特殊情况。 卡迈克尔数卡迈克尔数都是伪素数，最小的卡迈克尔数是561。它满足费马小定...
2019-02-13 00:01:35
2007
原创 【ICPC模板】高精度平方根
牛顿迭代法实现公式：核心：求与横坐标交点求导：牛顿迭代公式：特别地：上述公式求解num的平方根。Java代码：public static BigDecimal sqrt(BigDecimal b, BigDecimal eps) { BigDecimal crt = new BigDecimal(b.toString()); Big...
2019-02-13 00:01:25
174
原创 【ICPC模板】Catalan Number (卡特兰数)
目录Catalan Number (卡特兰数)通项公式递推关系渐进关系相关问题卡特兰数扩展问题Catalan Number (卡特兰数)通项公式其中Cn表示Catalan数序列的第n项。上述通项公式可以被理解为：在一个二维直角坐标平面内，从(0, 0)点出发走到(2n, 0)点的路径数，这条路径要求对于任意点(x, y)对于其横坐标相邻点的纵坐标差值的绝...
2019-02-13 00:01:13
370
原创 【ICPC模板】康托展开
由一个排列计算它是全排列中的第几个排列的方法。公式中x!表示x的阶乘，如果将排列元素写成一行，则a[n]表示从右向左数的第n个数，在其左边没有出现过且比当前数小的数的个数。如3 5 2 1 4中，比3小的数有2和1，一共2个，则a[5] = 2；到5时，比5小的且没有在它左边出现过的数有1, 2, 4，一共3个，则a[4] = 3……可以发现对于字典序最小的排列如1 2 3 4 5...
2019-02-13 00:01:03
354
原创 【ICPC模板】欧拉定理
费马小定理是欧拉定理的一个特殊情况，欧拉定理如下：其中φ(n)是n的欧拉函数值，表示小于n的正整数中满足gcd(n, x) = 1的数x的个数，可以理解为小于n且与n互素的整数的个数，需要特别注意整数1也满足与n的最大公约数为1的条件，因此它也被计数在内。...
2019-02-13 00:00:44
517
原创 ACM-ICPC模板整理
备注其一：正在整理中，内容不全，部分代码测试次数较少或还未在OJ上尝试，可能会有代码不健全的情况发生。备注其二：部分图片来自百度百科、wiki百科。备注其三：CSDN一天只能上传十篇blog...只能慢慢传了。备注其四：中间修改了（咕咕咕）了好长时间，目录又发生了一些变化。。。友情链接：https://blog.csdn.net/Adolphrocs/article/details...
2019-02-13 00:00:26
1512
原创 【ICPC模板】费马小定理 (Fermat's little theorem)
对于素数p，有下图所示同余式成立：更多情况下，写作下面的等价形式：注意：费马小定理的逆命题为假，也就是说，满足上式的数p不一定是素数，这样的合数被称为伪素数，因此不能使用这个定理来判定素性。...
2019-02-12 14:44:18
318
原创 【ICPC模板】费马大定理 (Le dernier théorème de Fermat)
也叫做费马最后定理 (Fermat's Last Theorem)，这一定理说对于n > 2的情况，下面的不定方程没有整数解。
2019-02-12 14:43:19
215
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人