当前位置:首页 >> 学科竞赛 >>

Noip整理


描述 fibonacci 数列 admin Description 著名的斐波那契数列
f[n]=1 f[n-1]+f[n-2] n=1,2 n>2

From

Flag 题号 模式 内存限制 代码限制

Accepted P1337 Normal (OI) 128MB 64KB 数论 / 数

>
现在求第 n 项,由于 f[n]可能很大,你只需要 输出 mod 32768的值即可。 输入格式 InputFormat 仅有一行,为 n,1<=n<=maxlongint 输出格式 OutputFormat 仅有一个数字,即答案

类型(?)

值值数论 / 数值

通过 提交

675人 1579次 43% 3

样例输入 SampleInput
3

通过率 难度

样例输出 SampleOutput
2

矩阵的快速幂是用来高效地计算矩阵的高次方的。 将朴素的 o (n) 的时间复杂度,降到 log(n) 。 原理: 一般一个矩阵的 n 次方,我们会通过连乘 n-1 次来得到它的 n 次 幂。 但做下简单的改进就能减少连乘的次数,方法如下: 把 n 个 矩 阵 进 行 两 两 分 组 , 比 如 : A*A*A*A*A*A (A*A)*(A*A)*(A*A) 这样变的好处是,你只需要计算一次 A*A,然后将结果(A*A)连 乘自己两次就能得到 A^6,即(A*A)^3=A^6。算一下发现这次一共乘 了 3 次,少于原来的 5 次。 其实还可以取 A^3 作为一个基本单位。原理都一样:利用矩阵 乘法的结合律,来减少重复计算的次数。 以上都是取一个具体的数来作为最小单位的长度, 这样做虽然能 够改进效率,但缺陷也是很明显的,取个极限的例子(可能有点不恰 当,但基本能说明问题) ,当 n 无穷大的时候,现在所取的长度其实 和 1 没什么区别。 所以就需要我们找到一种与 n 增长速度” 相适应 “的” 单位长度,这点是我们要思考的问题。 既然要减少重复计算,那么就要充分利用现有的计算结果,怎么 充分利用计算结果呢?这里考虑二分的思想。 。 比如 A^19 => (A^16)*(A^2)*(A^1) ,显然采取这样的 =>

方式计算时因子数将是 log(n)级别的(原来的因子数是 n),不仅这样, 因子间也是存在某种联系的, 比如 A^4 能通过(A^2)*(A^2)得到, A^8 又能通过(A^4)*(A^4)得到,这点也充分利用了现有的结果作为有利 条件。 即为以下方法: while (x<>0) do begin if x mod 2=1 then mul(a,b,a); x:=x div 2; mul(b,b,b); end; f[n]:=f[n-1]+f[n-2] 由矩阵乘法定义得出 //否则求平方 //若为奇数求一次方

?0 ? ?0
?1 ? ?0
?1 ? ?0

1? ?0 * ? ? 0? ?1
1? ?0 * ? ? 0? ?1
2? ?0 * ? ? 0? ?1

1? ? ? 1?
1? ? ? 1?
1? ? ? 1?

?1 ? ?0
?1 ? ?0
?2 ? ?0

1? ? 0?
2? ? 0?
3? ? 0?

则第 n 项为计算出的左上角的数

? fi ? ?0

f i ?1 ? ? f 0 ??? 0 ? ? 0

f1 ? ? 0 ? *? 0 ? ?1

1? ? 1?

i

(公式编辑器好难用。 。 。 。 。 。 ) type arr=array[1..2,1..2] of int64; var x,p:int64; a,b,c,w:arr; procedure mul(var a,b,c:arr); var i,j,k,n:longint; begin n:=2; fillchar(w,sizeof(w),0); for i:=1 to n do for j:=1 to n do for k:=1 to n do w[i][j]:=(w[i][j]+a[i][k]*b[k][j]) mod p; for i:=1 to n do for j:=1 to n do c[i][j]:=w[i][j]; end; begin p:=32768;

readln(x); a[1,1]:=0;a[1,2]:=1;a[2,1]:=0;a[2,2]:=0; b[1,1]:=0;b[1,2]:=1;b[2,1]:=1;b[2,2]:=1; while (x<>0) do begin if x mod 2=1 then mul(a,b,a); x:=x div 2; mul(b,b,b); end; writeln(a[1][1]); End. Kosaraju 算法 Kosaraju 算法过程上并不复杂。要求解一个有向图的强连通分量,第 一步: 在该图的逆图上运行 DFS, 将顶点按照后序编号的顺序放入一 个数组中 (显然, 这个过程作用在 DAG 上得到的就是一个拓扑排序) ; 第二步:在原图上,按第一步得出的后序编号的逆序进行 DFS。也就 是说,在第二次 DFS 时,每次都挑选当前未访问的结点中具有最大 后序编号的顶点作为 DFS 树的树根。

Kosaraju 算法的显著特征是,第一,引用了有向图的逆图;第二,需 要对图进行两次 DFS(一次在逆图上,一次在原图上) 。而且这个算 法依赖于一个事实:一个有向图的强连通分量与其逆图是一样的(即

假如顶点任意顶点 s 与 t 属于原图中的一个强连通分量,那么在逆图 中这两个顶点必定也属于同一个强连通分量, 这个事实由强连通性的 定义可证) 。由于算法的时间取决于两次 DFS,因此时间复杂度,对 于稀疏图是 O(V+E),对于稠密图是 O(V?),可见这是一个线性算法。 Kosaraju 的结论是,在第二次 DFS 中,同一棵搜索树上的结点属于 一个强连通分量。

证明:假设顶点 s 与 t 属于第二次 DFS 森林(注意,第二次是在原图 上搜索)的同一棵树,r 是这棵树的根结点。那么有以下两个事实: 一,原图中由 r 可达 s,这蕴含在逆图中从 s 到 r 有一条路径;二,r 在逆图中的后序编号大于 s (r 是树根,因此 r 的后序编号比树中所有 的其他结点的都大) 。现在要证明的是在逆图中从 r 到 s 也是可达的。

好,两个事实结合起来:一,假设逆图中 r 到 s 不可达,且 s 到 r 存 在路径,那么这条路径将使 s 的后序编号比 r 大,与事实一矛盾,排 除;二,假设逆图中 r 到 s 存在路径,正是这条 r 到 s 的路径使得 r 有更大的后序编号,则 r 与 s 是强连通的,假设成立(看上去比较勉 强,个人认为这应该是一个空证明) 。显然,两个事实导出一个结论: 逆图中,r 与 s 互相可达。同理,r 与 t 也互相可达,根据传递性,第 二次 DFS 森林中同一棵树中的所有顶点构成一个强连通分量。

另一方面, 会不会一个强连通分量的所有顶点没有出现在第二次 DFS

森林的同一颗树中呢?答案是:不会。因为根据 DFS 的性质,如果 r 与 s 强连通,那么由 r 开始的 DFS 必定能搜到 s。

证毕。

可见 Kosaraju 的方法能够找出有向图的强连通分量, 那么为什么这个 方法可行呢?或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个顺序的逆序进行搜索,这 保证每次选取的根结点(刚才证明中的 r 结点)都具有未访问结点中 最大的后序编号,则搜索中拓展的结点的后序编号都比根结点小,这 样也就满足了事实二。

补充:Kosaraju 算法虽然是线性的,但是需要两次 DFS,跟另外两个 著名的求解强分量的算法相比, 这是一个劣势。 但是 Kosaraju 算法有 个神奇之处在于:计算之后的强分量编号的顺序,刚好是该有向图 K(D)(kernel DAG, 核心 DAG)的一个拓扑排序!因此 Kosaraju 算法同时提供了一个计算有向图 K(D)拓扑排序的线性算法。这个结 果在一些应用中非常重要。

var a:array[1..5000,1..5000] of longint; b,flag:array[1..5000] of longint; n,i,j,m,k,x,y:longint; procedure dfs(x:longint); var j:longint; begin flag[x]:=1; for j:=1 to n do if (flag[j]=0) and (a[x][j]>0) then dfs(j); inc(m); b[m]:=x; end; procedure fill(x,k:longint); var j:longint; begin flag[x]:=k;

for j:=n downto 1 do if (flag[b[j]]=0) and (a[b[j]][x]>0) then fill(b[j],k); end; begin assign(input,'in.in'); reset(input); readln(n); for i:=1 to n do begin readln(x,y); a[x][y]:=1; end; m:=0; fillchar(flag,sizeof(flag),0); for i:=1 to n do if flag[i]=0 then dfs(i); fillchar(flag,sizeof(flag),0); k:=0; for i:=n downto 1 do if flag[b[i]]=0 then begin inc(k);

fill(b[i],k); end; for i:=1 to k do begin for j:=1 to n do if flag[j]=i then write(j,' '); writeln; end; close(input); End.

Tarjan
【算法思想】 用 dfs 遍历 G 中的每个顶点,通 dfn[i]表示 dfs 时达到顶点 i 的时 间,low[i]表示 i 所能直接或间接达到时间最小的顶点。(实际操作中 low[i]不一定最小,但不会影响程序的最终结果) 程序开始时,time 初始化为 0,在 dfs 遍历到 v 时, low[v]=dfn[v]=time++, v 入栈(这里的栈不是 dfs 的递归时系统弄出来的栈)扫描一遍 v 所 能直接达到的顶点 k,如果 k 没有被访问过那么先 dfs 遍历 k, low[v]=min(low[v],low[k]);如果 k 在栈里,那么 low[v]=min(low[v],dfn[k])(就是这里使得 low[v]不一定最小,但不会 影响到这里的 low[v]会小于 dfn[v])。扫描完所有的 k 以后,如果

low[v]=dfn[v]时,栈里 v 以及 v 以上的顶点全部出栈,且刚刚出栈的 就是一个极大强连通分量。 【大概的证明】

1.

在栈里,当 dfs 遍历到 v,而且已经遍历完 v 所能直接到达的

顶点时,low[v]=dfn[v]时,v 一定能到达栈里 v 上面的顶点: 因为当 dfs 遍历到 v,而且已经 dfs 递归调用完 v 所能直接到 达的顶点时(假设上面没有 low=dfn) ,这时如果发现 low[v]=dfn[v], 栈上面的顶点一定是刚才从顶点 v 递归调用时进栈的, 所以 v 一定能 够到达那些顶点。 2 .dfs 遍历时,如果已经遍历完 v 所能直接到达的顶点而 low[v]=dfn[v],我们知道 v 一定能到达栈里 v 上面的顶点,这些顶点 的 low 一定小于 自己的 dfn,不然就会出栈了,也不会小于 dfn[v], 不然 low [v]一定小于 dfn[v],所以栈里 v 以其 v 以上的顶点组成的子 图是一个强连通分量, 如果它不是极大强连通分量的话 low[v]也一定 小于 dfn[v], 所以栈里 v 以其 v 以上的顶点组成的子图是一个极大强 连通分量。 【时间复杂度】 因为所有的点都刚好进过一次栈, 所有的边都访问的过一次, 所 以时间复杂度为 O(n+m)

{ DFN[u]=Low[u]=++Index // 为节点 u 设定次序编号和 Low 初值 Stack.push(u) for each (u, v) in E if (v is not visted) tarjan(v) // 将节点 u 压入栈中 // 枚举每一条边 // 如果节点 v 未被访问过 // 继续向下找

Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点 v 还在栈内

Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) repeat v = S.pop // 将 v 退栈,为该强连通分量中一个顶点 print v until (u== v) } // 如果节点 u 是强连通分量的根

Tarjan 算法 Var a:array[0..5000,0..5000] of boolean; stack,dfn,low,gpoint:array[0..5000] of longint; v:array[0..5000] of boolean; top,root,ans,all,i,p,q,n,m:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure tarjan(p:longint); var i:longint; begin inc(all); low[p]:=all; dfn[p]:=all; inc(top); stack[top]:=p;

v[p]:=true; for i:=1 to n do if a[p,i] then begin if dfn[i]=0 then begin tarjan(i); low[p]:=min(low[p],low[i]); end; if v[i] then low[p]:=min(low[p],dfn[i]); {if (low[i]>=dfn[p]) and (p<>1) then gpoint[p]:=gpoint[p]+1 else if p=1 then root:=root+1 else low[p]:=min(low[p],dfn[i]);} end; {else if v[i] then low[p]:=min(low[p],dfn[i]); if low[p]=dfn[p] then begin //求割点

repeat v[stack[top]]:=false; write(stack[top],' '); dec(top); until stack[top+1]=p; writeln; end;} // 求强连通分量

end; {procedure print; var i:longint; begin if root>1 then ans:=ans+1; for i:=2 to n do begin if gpoint[i]>0 then begin ans:=ans+1; writeln(i); end; end;

writeln(ans); end;} begin assign(input,'in.in'); assign(output,'out.out'); reset(input); rewrite(output); readln(n,m); fillchar(a,sizeof(a),false); fillchar(v,sizeof(v),false); all:=0;top:=0; for i:=1 to m do begin readln(p,q); a[p,q]:=true; end; for i:=1 to n do if dfn[i]=0 then tarjan(i); // print; close(input); close(output); end. // 求割点


相关文章:
Noip整理
Noip整理 暂无评价 8页 2下载券 noip 每日整理 暂无评价 4页 1下载券 NOIp每日整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代...
NOIp每日整理
["扫地"杯 III day1]诡异的数学题 From liouzhou_101 背景 Background “扫地”杯 III NOIP2012模拟赛 day1 第一题描述 Description liouzhou_101从 NOI 归来...
Noip整理
Noip整理_学科竞赛_高中教育_教育专区。团伙 背景 Background From BearHsu 经典题目描述 Description 1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他 ...
Noip整理
Noip整理 暂无评价 12页 2下载券 noip 每日整理 暂无评价 4页 1下载券 NOIp...[NOIP2010]乌龟棋 From NOIP2010提高组复赛第二题 描述 Description 小明过生日...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
noip 每日整理
Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整...
NOIP算法整理
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
2016.10.1 学习整理
2016.10.1 学习整理_教育学_高等教育_教育专区。2016.10.1 期清北学堂整理 ...(NOIP 不过多涉及这方面的知识) 并查集(这才是 NOIP 真正用得到的) 并查集是...
NOIP模板代码(C++)
NOIP模板代码(C++)_计算机软件及应用_IT/计算机_专业资料。NOIP模板代码,精心整理,包含DP,数论,图论和常用数据结构,以及常用STL容器和库函数。...
NOIP2014 题解
NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头...(x+p)在展开后必然可以整理成 f(x)+T,其中 T 为关于 p 的一个多项式, ...
更多相关标签:
noip2016 | noip2016提高组复赛 | noip2015提高组复赛 | noip2016普及组复赛 | noip吧 | noip2016复赛成绩 | noip2016复赛 | 2016noip复赛成绩查询 |