4 DZYO

尚未进行身份认证

我要认证

Never stop

等级
TA的排名 5k+

实Jordan标准形的推导

众所周知,任意复矩阵有惟一Jordan标准形。对于实矩阵,设其初等因子为p1s1(λ),...,pnsn(λ)p_1^{s_1}(\lambda),...,p_n^{s_n}(\lambda)p1s1​​(λ),...,pnsn​​(λ),影响构造Jordan块的只有形如(x2+px+q)n(x^2+px+q)^n(x2+px+q)n形式的初等因子,其中p2−4q<0p^2-4q<0p...

2020-04-25 12:29:58

拉格朗日乘子法

a brief proof to the Lagrange Multiplier Method

2020-04-14 16:06:26

《国际最佳数学征解问题分析》P77(单位根反演+生成函数)

问题给定x1,...,xnx_1,...,x_nx1​,...,xn​,令xi(1)=xi+xi+12x_i^{(1)} = \frac{x_i+x_{i+1}}{2}xi(1)​=2xi​+xi+1​​,i=1,...,ni=1,...,ni=1,...,n,其中xn+1=xix_{n+1}=x_ixn+1​=xi​.归纳地定义xi(k)=xi(k−1)+xi+1(k−1)2,i=1,......

2019-10-06 19:33:23

Tietze扩张定理

一个延拓函数的方法

2020-04-05 16:36:00

PCA & SVD & 极分解 简介

A brief intro to PCA and SVD decomposition.

2020-03-28 20:13:21

Alpha-Beta搜索剪枝最优效率分析

A naive analysis of the best efficiency of Alpha-beta pruning.

2020-03-16 16:17:49

哈密顿-凯莱(Hamilton-Cayley)定理的两种简要证明

Two brief proofs of Hamilton-Cayley theorem.

2020-03-11 09:48:11

《线性代数》 李炯生\查建国\王新茂 中国科学技术大学 第2版 部分习题答案

百度了一圈没有靠谱点的答案,于是便有了这篇博客。。。文章目录第一章 多项式1.3 整除性与最大公因式习题3习题101.5 实系数与复系数多项式习题1习题2.(4)习题101.6 整系数与有理系数多项式例1例2习题2习题6习题7习题81.8 对称多项式习题3习题6习题8,10习题11.第一章 多项式1.3 整除性与最大公因式习题3证明: 当n=6m+5n=6m+5n=6m+5时,多项式x2...

2019-10-31 18:06:06

Burnside引理的简要证明

A brief proof of Burnside's theorem

2019-09-09 21:29:22

常系数齐次线性递推优化矩阵快速幂

一般矩阵快速幂的形式 : f(n)=∑i=1k1aif(n−i)+∑i=1k2big(n−i)+bf(n)=\sum_{i=1}^{k_1} a_if(n-i)+\sum_{i=1}^{k_2}b_ig(n-i)+b 可以做到k3lognk^3 \log n的常数递推,不过有更加快速的方法。若有如下转移 f(n)=∑i=1kaif(n−i)f(n)=\sum_{i=1}^k a_if(n-i)

2019-08-11 13:16:02

集训队作业2018: 复读机(生成函数)

题意:群里有kkk个不同的复读机。为了庆祝平安夜的到来,在接下来的nnn秒内,它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是,一个复读机只有总共复读了ddd的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐(k≤1000,d≤3)(k \le 1000, d \le 3)(k≤1000,d≤3)。题解:挺妙的,一个人的生成函数是∑i=0∞[d∣i]i!xi\s...

2019-01-18 16:06:02

集训队作业2018: 喂鸽子(min-max容斥)

题意:小Z是养鸽子的人。一天,小Z给鸽子们喂玉米吃。一共有n只鸽子,小Z每秒会等概率选择一只鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量≥k≥k≥k。 小Z想要你告诉他,期望多少秒之后所有的鸽子都饱了。题解:min-max容斥枚举下集合大小,FFT预处理一下系数算min的期望即可。#pragma GCC optimize(2)#include <bits/stdc++...

2019-01-15 16:09:53

集训队作业2018: 取名字太难了(FFT)

题意:大概是求∏i=1n(x+i)\prod_{i=1}^n(x+i)∏i=1n​(x+i)系数模ppp意义下的分布。题解:分为(∏i=1p−1(x+i))⌊np⌋(\prod_{i=1}^{p-1}(x+i))^{\lfloor\frac{n}{p}\rfloor}(∏i=1p−1​(x+i))⌊pn​⌋,以及(∏i=1n mod&VeryThi...

2019-01-14 19:23:49

集训队作业2018: 树(点分治+K短路)

题解:最近学数分学到意识模糊,做到OI题冷静一下。联通块强制选根,然后用dfs序转化为一个路径然后就是做K短路了。用点分治即可在图大小为O(nlog⁡n)O(n \log n)O(nlogn)的图上做K短路,时间复杂度O(nlog⁡2n+klog⁡k)O(n \log ^2 n + k\log k)O(nlog2n+klogk)。#include <bits/stdc++.h>...

2019-01-12 16:50:06

Codeforces 802C :Heidi and Library (hard)(网络流)

传送门题解:比较简单的建图法就是看做小于k条流在一个n∗nn*nn∗n序列上流,其中一些位置是必须流的,然后做个上下界费用流。不过注意到肯定有一种方案使得这小于kkk条流是不相交的,于是可以直接看做有nnn个点,每个点拆点连−∞-\infty−∞的边,然后规定这个点必须是aia_iai​,然后跑个最小费用可行流,这样nnn个−∞-\infty−∞必定流满,此外其他加起来最小。最后加个n∗∞...

2018-11-30 17:33:51

Codeforces 806F:Test Data Generation(组合数学)

传送门题解:相当于是要求:∑u∑i=1⌊n2u⌋[i为奇数]∑j=1n−1[j为偶数](i−1j)\sum_{u}\sum_{i=1}^{\lfloor\frac{n}{2^u}\rfloor}[i为奇数] \sum_{j=1}^{n-1}[j为偶数] \binom{i-1}{j}u∑​i=1∑⌊2un​⌋​[i为奇数]j=1∑n−1​[j为偶数](ji−1​)然后注意这个jjj比较小,我...

2018-11-30 15:43:58

UOJ#433. 【集训队作业2018】串串(循环串/回文串)

传送门题解:这道题主要用到的几个性质(具体证明可以看题解):1.弱双回文串SSS的某个双回文划分ababab,满足aaa是SSS的最长回文前缀,或者bbb是SSS的最长回文后缀。2.弱双回文串SSS若有两个弱回文划分,则SSS为整周期串。3.弱双回文串SSS的周期为ttt,则其有∣S∣t\frac{|S|}{t}t∣S∣​个不同的弱回文划分。我们先计算本质不同的双回文串划分,然后减去算...

2018-11-27 20:26:49

集训队作业2018: 通信(区间DP)

题意:题解:想到了大概思路就是不会有相交的非链上的边,然而有一堆细节就鸽了。然后看题解其实就是暂时忽略两边的值来区间DP就行了,设置的状态还挺妙的,中间记个前缀后缀min优化一下,时间复杂度O(n3)O(n^3)O(n3)。#include <bits/stdc++.h>using namespace std;#define opt(x) memset(x,0x3f,si...

2018-11-27 11:36:00

UOJ#429. 【集训队作业2018】串串划分(循环串)

传送门题解:考虑设dpidp_idpi​表示以iii结尾的前缀的划分方案数,因为有2条件的限制,可以得到容斥式子:dpi=∑j(−1)C(Sj+1,i)dpjdp_i = \sum_{j}(-1)^{C(S_{j+1,i})}dp_jdpi​=j∑​(−1)C(Sj+1,i​)dpj​C(S)C(S)C(S)表示SSS的最小循环节循环的次数,相当于从前面某个位置转移过来,中间全用相同的串划...

2018-11-24 22:41:54

Atcoder AGC019简要题解

传送门Reverse and Compare发现两个串如果翻转后一样且中心不一样,则必定有一个是回文串。然后就只用统计两端字母不同的串的个数了。#include <bits/stdc++.h>using namespace std;typedef long long LL; const int N=2e5+50;char ch[N];int n,cnt[26],s;...

2018-11-22 09:10:59

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享小兵
    分享小兵
    成功上传3个资源即可获取