/* 给定n个数的数列,要求枚举长为k的区间,求出每个区间的最长上升子序列长度 首先考虑给定n个数的数列的LIS求法:从左往右枚举第i点作为最大点的贡献, 那么往左找到第一个比a[i]大的数,设这个数下标l,那么[l+1,i-1]的后继显然是i 那么[l+1,i-1]区间,和包括第i个数的LIS都可以+1,处理完所有点后求[1,n]区间的最大值即可 区间更新显然用线段树解决,线段树叶子结点维护第i个位置被加次数,即以第i个结点为起点的LIS长度 本题是枚举长为k的区间,求每个区间的LIS,那么只

/* 题意:给定一个长度为n的序列a. 两种操作: 1.给定区间l r 加上某个数x. 2.查询区间l r sigma(fib(ai)) fib代表斐波那契数列. 思路: 1.矩阵操作,由矩阵快速幂求一个fib数根据矩阵的乘法结合率,A*C+B*C=(A+B)*C; 这样可以通过线段树维护某个区间2*1矩阵的和. 2.时限卡的紧...用我的矩阵乘法板子TLE了.所以把板子里边的三重循环改成手工公式... 3.注意(a+b)%mod.这种,改成if(a+b>=mod)a+b-mod这种形式时间几乎

题目链接 \(998244353\)写成\(99824435\)然后调这个线段树模板1.5h= = 以后要注意常量啊啊啊 \(Description\) 每个位置有一个\(3\times3\)的矩阵,要求支持区间赋值和求区间乘积. 输出答案对\(998244353\)取模后的结果. \(n,q\leq10^5\). \(Solution\) 裸的线段树+矩阵快速幂是\(O(3^3q\log^2n)\)的,因为维护区间乘的话,区间赋值为矩阵\(A\)的时候要赋值\(A^{r-l+1}\),带一个快

区间\(dp\)提升复习 不得不说这波题真的不简单... 技巧总结: 1.有时候转移可以利用背包累和 2.如果遇到类似区间添加限制的题可以直接把限制扔在区间上,每次只考虑\([l,r]\)被\([i,j]\)完全包含的情况 [BZOJ4897] [Thu Summer Camp2016] 成绩单 典型的利用背包转移,\(dp[i][j]\)表示处理完这段\([i,j]\)区间的答案 转移时一段区间可以被先处理掉或者直接从已经处理完的\(dp[i][j]\)中取过来,这个可以用一个背包维护 con

import numpy as np lis = np.mat([[1,2,3],[3,4,5],[4,5,6]]) print(np.linalg.inv(lis)) # 求矩阵的逆矩阵 [[-1.2009599e+16 3.6028797e+16 -2.4019198e+16] [ 2.4019198e+16 -7.2057594e+16 4.8038396e+16] [-1.2009599e+16 3.6028797e+16 -2.4019198e+16]] print(lis.trans

字符串: 1.广义后缀自动机(大小为\(m\))上跑一个长度为\(n\)的串,所有匹配位置及在\(parent\)树上其祖先的数量的和为\(min(n^2,m)\),单次最劣是\(O(m)\). 但是如果跑多个串,总长为\(n\),可以证明所有串长相等的时候复杂度更劣,设有\(k\)个串,那么复杂度为:\(O(k(n/k)^2)\),这个时候\(k=\frac{n}{\sqrt{m}}\)最劣,是\(O(n\sqrt{m})\) 2.反串\(parent\)树就是压缩节点后缀树. 3.后缀树可以

https://www.douban.com/group/topic/11115261/ 在过去的一年中,我一直在数学的海洋中游荡,research进展不多,对于数学世界的阅历算是有了一些长进. 为什么要深入数学的世界 作为计算机的学生,我没有任何企图要成为一个数学家.我学习数学的目的,是要 想爬上巨人的肩膀,希望站在更高的高度,能把我自己研究的东西看得更深广一些.说起来,我在刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅 程.我的导师最初希望我去做的题目,是对appearance和m

作者:林达华 一.为什么要深入数学的世界 作为计算机的学生,我(原作者)没有任何企图要成为一个数学家.我学习数学的目 的,是要想爬上巨人的肩膀,希望站在更高的高度,能把我自己研究的东西看得更深广一些.说起来,我在刚来这个学校的时候,并没有预料到我将会有一个深入数 学的旅程.我的导师最初希望我去做的题目,是对appearance和motion建立一个unified的model.这个题目在当今Computer Vision中百花齐放的世界中并没有任何特别的地方.事实上,使用各种Graphical M

原文网址:http://www.guokr.com/post/442622/ 在过去的一年中,我一直在数学的海洋中游荡,research进展不多,对于数学世界的阅历算是有了一些长进. 为什么要深入数学的世界 作为计算机的学生,我没有任何企图要成为一个数学家.我学习数学的目的,是要 想爬上巨人的肩膀,希望站在更高的高度,能把我自己研究的东西看得更深广一些.说起来,我在刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅 程.我的导师最初希望我去做的题目,是对appearance和motion建

Time Limit: 1000 ms   Memory Limit: 256 MB Description 给定一个01串 $S_{1 \cdots n}$ 和 $Q$ 个操作. 操作有两种类型: 1.将 $[l, r]$ 区间的数取反(将其中的0变成1,1变成0). 2.询问字符串 $S$ 的子串 $S_{l \cdots r}$ 有多少个不同的子序列.由于答案可能很大,请将答案对 $10^9 + 7$ 取模. 在数学中,某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置

观察到列数只有15,可以想到对于每一列维护一颗线段树 sum表示该区间与目标矩阵中该区间相同元素个数 lazy表示该区间应被修改成什么颜色 g即目标矩阵中该区间白色格子的个数 显然一个区间的sum=区间长度-g(修改为0时) 或 g(修改为1时) #define RG register #include<cstdio> using namespace std; ; int n,m,q,X,Ans; ]; inline int read() { RG ,w=;RG char ch=getchar

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明网址: http://www.penglixun.com/study/science/mit_math_system.html 目录 (Contents) 1 为什么要深入数学的世界 2 集合论:现代数学的共同基础 3 分析:在极限基础上建立的宏伟大厦 3.1 微积分:分析的古典时代——从牛顿到柯西 3.2 实分析:在实数理论和测度理论上建立起现代分析 3.3 拓扑学:分析从实数轴推广到一般空间——

麻省理工( MIT)大神解说数学体系 http://blog.sina.com.cn/s/blog_5ff4fb7b0102e3p6.html 其实每一门学科都应该在学习完成后,在脑子里面有一个体系,比如物理体系.化学体系.数学体系等等.我们学习一门课程的收获,不是期末考试能考多少分,能拿多少奖学金,能获得高GPA,而是要真正建立起这个学科的体系,为未来的深入学习或者研究打基础.做准备. 以下是牛人的数学体系: 在过去的一年中,我一直在数学的海洋中游荡,research进展不多,对于数学世界的阅

Description 给定一个数列,维护两种操作 操作 \(1\),将区间 \([l,r]\) 的数字统一加 \(x\). 操作 \(2\),求 \(\sum \limits_{i=l}^r f(val[i])\),其中 \(f(i)\) 表示斐波那契数列的第 \(i\) 项.' 答案对 \(10^9+7\) 取模. Solution 线段树维护矩阵. 因为是斐波那契数列,容易想到用矩阵快速幂来求这个东西. 想这样做的话,要想清楚两个问题: 因为题目中求的是和,那么知道 \([l,mid]\)

http://www.lydsy.com/JudgeOnline/problem.php?id=4826 吐槽一下bzoj这道题的排版是真丑... 我还是粘洛谷的题面吧... 提供p1的攻击力:i,j 位置的数是区间[i,j]的最大值和次大值 提供p2的攻击力:i,j位置的数有一个是区间[i,j]的最大值,另一个不是次大值 记录L[i].R[i] 分别表示i左右第一个大于k[i]的位置 p1的贡献: 1.点对(L[i],R[i])    2.点对(i,i+1) p2的贡献: 1.点对(L[i],

题目大意:给你一颗$n$个点的树,点有点权,有$m$次操作,每次操作给定$x$,$y$,表示修改点$x$的权值为$y$. 你需要在每次操作之后求出这棵树的最大权独立集的权值大小. 数据范围:$n,m≤1e5$ 我们显然可以得出一个$O(nm)$的暴力做法,每次修改完后$dp$一次,然而这个显然会超时. 考虑当树退化成链时的简单做法. 我们用线段树维护每个区间的答案.对于区间$[l,r]$,我们维护一个$2×2$的答案矩阵$ans$. 设$ans[0][0]$表示区间左端点可能被选择,右端点一定不

E:01 串 链接 分析: 线段树维护转移矩阵.每个节点是一个矩阵,区间内的矩阵乘起来就是答案矩阵.矩阵乘法满足结合律,所以线段树维护. 代码: #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<cctype> #include<set> #include<queue&g

day-1 打点行囊,从学校出发去火车站 day0 在火车上一觉醒来便快到了北京,直接前往了宾馆安置 下午报道,一脸向往地第一次走入清华园,感觉十分的梦幻,心里一直喃喃:"希望以后也能经常在这条路上徘徊" 报道和试机地点是最向往的软工学院,发了狗牌和一件白色纪念衫 试机 依旧是\(WC\)时操作蛋疼的\(ubuntu\),这次的版本似乎不能直接新建文件... \(T1\)是一个\(BIT\) + 逆序对个数 \(T2\)是去年毒瘤计算几何提答题. 晚上十分紧张地入睡了 day1 一早醒

蛋疼啊,本次只做出了一道题目...渣爆了... 妈蛋,,卡题之夜..比赛结果是1道题,比赛完哗啦哗啦出4道题.. A acdream1191 Dragon Maze 题意: 给一个迷宫,给出入口坐标和出口坐标,要求从入口到出口的步数尽可能少,如果有多种方案,则要求获得的分数尽可能多,获得的分数为经过的方格的数字之和 思路: bfs求最小步数,每走一步更新一下走到这个格子的最大权值 #include <bits/stdc++.h> using namespace std; typedef lon

题目描述: 对于斐波那锲数列f(0)=0,f(1)=1,....求f(f(n)的值 0<=n<=10^100 给出T组数据,每行一个n 输出n行 f(f(n)) 样例输入: 4 0 1 2 6 输出: 0 1 1 21 思路: 原来菲波那切数列是个纯周期数列,对于每一个模数MOD,它会有一个最小正周期,那么我们可以把这个很大的数n 或者 f(n) 映射到 一个的小区间,然后矩阵快速幂就OK了 关于哪个最小正周期的值,暴力去求就行了. #include<iostream> #incl