什么是主席树

主席树:可持久化线段树,特点是每次修改都新建一颗新树,由于单点修改最多影响$\log n$个节点,因此只需要新建一条链,挂在原树上

问题:[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本

这是一道板子题,但是此题没有体现主席树的经典应用,代码如下:

阅读全文

普通的快速幂

问题[COGS 1433]圣庙里的汉诺塔

计算$a^b\mod m$,其中$0\leq a,b\leq10^{16}$。

我们可以写出如下的暴力求幂程序,复杂度$O(n)$:

typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
  	ll ans=1;
  	while(b--)
      	ans=(ans*a)%m;
  	return ans;
}

不过注意到对于任意正整数k,我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$(可以递推出来),然后再用$\log b$次乘法将其合并起来,复杂度为$O(\log n)$,代码如下:

ll fast_pow_mod(ll a,ll b,ll m)
{
    ll ans=1;
  	while(b)
    {
      	if(b&1)
          	ans*=a;
      	a*=a;
      	b>>=1;
    }
  	return ans;
}

由快速幂魔改的快速乘

问题:[COGS 2037]Asm.def大点兵

由于$a\times b$可能溢出,因此不能直接乘起来再取膜,考虑到一个事实:
$$
a^b=
\begin{cases}

1 & b=0 \\
\underbrace { a \times \cdots \times a }_b & b \ge 1

\end{cases}
$$
$$
a\times b=
\begin{cases}
0&b=0
\underbrace{a+\cdots+a}_b&b\not=0
\end{cases}
$$
所以我们把上面的代码稍微改一改就好了:

阅读全文
如题,Blog迁移至Github Pages,因为我懒233 测试一下公式: $$ \begin{cases} dp\left(1\right)=1 \ dp\left(i\right)=\sum_{j\in\left[max(i-r,1),i-l\right]&h(j)\in\left[h(i)-t,h(i)+t\right]}dp(j) \end{cases} $$ $$ \begin{cases} dp(i)=1&outdgree(i)=0\ dp(i)=\max{dp(j)}+outdgree(i)&(i,j)\in E \end{cases} $$ 看起来Katex跑的不错嘛2333 UPDATE 2017/5/29 添 阅读全文

题目

★★☆
输入文件:zootopia.in 输出文件:zootopia.out 简单对比

时间限制:1 s 内存限制:32 MB

【题目描述】

  1. 物理学要求:为了稳定和美观,半径大的蛋糕必须在放在半径小的蛋糕下面。
  2. Mr.Big的钦定要求:编号小的蛋糕必须放在编号大的蛋糕下面。

你需要帮他制定一个使多层蛋糕总体积最大的方案。

你只需要计算出最大的总体积即可。
注意:两个半径相同的蛋糕不能放在一起

【输入格式】

第一行一个整数n,

接下来n行,第i+1行两个整数R,H分别表示编号为i的蛋糕的半径和高度。

【输出格式】

只有一行一个整数,为最大总体积,由于出题人懒得写评测插件,你需要精确到小数点后2位

题解

思路

此题乍一看是普通的最长上升/下降子序列,然而$O(n^2)$的做法会挂掉,所以要用$O(nlogn)$的做法

阅读全文

综述

我的Blog基于Hexo和Nginx搭建,本来是很简单的东西,但是由于我太弱了,搞了足足一天233

步骤

在服务器上安装Nginx

这步比较简单,直接安装一个LNMP的包即可

阅读全文
Finally!! Margatroid’s Blog
title: 矩阵快速幂 date: 2017/9/18 07:46:25 categories: - OI tags: - OI - 数学 - 矩阵运算 - COGS --- 矩阵快速幂.md 前置技能 矩阵乘法 复杂度为$O(n^3)$,有复杂度稍低的分治写法,不过意 阅读全文