4 DZYO

尚未进行身份认证

Never stop

等级
TA的排名 5k+

《线性代数》 李炯生\查建国\王新茂 中国科学技术大学 第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

UOJ#428. 【集训队作业2018】普通的计数题(牛顿迭代)

传送门题解:把0操作看做是叶子,1操作看做非叶节点,一个操作在另一个操作删除,则另一个操作为这个操作的父亲,于是转化成了满足以下条件的nnn个点的树的计数:1.父亲标号>儿子。2.若一个点为非叶节点,记其儿子中叶子节点的数量为TTT,则若其儿子中有非叶节点,T∈AT\in AT∈A,否则T∈BT \in BT∈B。首先可以发现的是BBB集合中有没有0都无所谓(因为必须选非空序列),...

2018-11-21 12:00:42

HDU6172:Array Challenge(Berlekamp-Massey算法)

传送门题解:大胆猜想有递推式,然后BM立水之。#include <bits/stdc++.h>using namespace std;const int RLEN=1<<18|1;inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+frea...

2018-11-19 18:45:14

Codechef:Walk on Tree/TREEWALK(Berlekamp-Massey算法)

传送门题解:O(n3log⁡k)O(n^3 \log k)O(n3logk)的优化应该都会。然后O(n2)O(n^2)O(n2)用BM求出递推式之后再O(n2log⁡k)O(n^2 \log k)O(n2logk)用特征多项式优化一下就行了。#include <bits/stdc++.h>using namespace std;const int RLEN=1<&a

2018-11-19 18:03:40

BZOJ1494: [NOI2007]生成树计数(Berlekamp-Massey算法)

传送门题解:直接打表+BM算出递推式,BM具体实现可以戳这里附上一份其丑无比的BM代码:const int L=4e2;namespace bm { int cnt,a[N],fail[N],delta[N]; vector <int> R[N]; inline void pt(vector <int> &vec) { for(int

2018-11-17 11:39:03

集训队作业2018:GAME(并查集)

题意:题解:把这个DP式子给列出来:fi=si+max⁡j{2∗aj−sj−fj}f_i = s_i + \max_j \{ 2*a_j-s_j- f_j\}fi​=si​+jmax​{2∗aj​−sj​−fj​}把这个后缀max⁡\maxmax记为mmm的话,每次就是m=max⁡{m,−2∗si−1−m}m=\max\{m,-2*s_{i-1}-m\}m=max{m,−2∗si−1​−...

2018-11-16 16:12:07

集训队作业2018: 青春猪头少年不会梦到兔女郎学姐(多限制容斥)

前言:虽然这道题的名字有点那啥,但是题还是很好的,听说是某道原题的加强版。题意:给定nnn种颜色的球,第iii种颜色的球数量为AiA_iAi​个,保证∑i=1nAi≤2∗105\sum_{i=1}^n A_i \le 2*10^5∑i=1n​Ai​≤2∗105,对于这所有(∑Ai)!∏Ai!\frac{(\sum_{A_i})!}{\prod A_i!}∏Ai​!(∑Ai​​)!​的排列,一...

2018-11-16 14:19:53

Codeforces 809E: Surprise me!(Mobius反演)

传送门题解:对于每个iii,处理出:fi=∑a∑b[(vala,valb)==i]φ(vala)φ(valb)dis(a,b)f_i=\sum_a\sum_b[(val_a,val_b)==i]\varphi(val_a)\varphi(val_b)dis(a,b)fi​=a∑​b∑​[(vala​,valb​)==i]φ(vala​)φ(valb​)dis(a,b)那么ans=∑ifiiφ...

2018-11-13 22:02:47

查看更多

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