ferryvan

F.R. | Blog


  • 首页

  • 归档

卡特兰数

发表于 2018-12-23
字数统计: 406 | 阅读时长 ≈ 2

先贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1000000007;

ll x[1020000];

ll qpow(ll num,ll pow)
{
ll ret=1;
if(pow==0) return ret;
while(pow)
{
if(pow&1) ret=(ret*num)%INF;
num=(num*num)%INF;
pow=pow>>1;
}
return ret;
}
int main()
{
ll n;
x[1]=1;
for(ll i=2;i<1019000;++i)
{
x[i]=((((i*4-2)*x[i-1])%INF)*(qpow(i+1,INF-2)%INF))%INF;
}
while(scanf("%d",&n)!=EOF)
printf("%d\n",x[n]);
return 0;
}

卡特兰数

令h(0)=1,h(1)=1,catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)h(1)+h(1)h(0)=11+11=2

h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5

另类递推式 :

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为:

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)

递推关系式:

在结果很大的时候我们对结果进行mod 1e9+7 运算

这个时候会产生一个问题,那就是模运算在除法下的变化

逆元

如果

则称a关于模p的乘法逆元为b

此时有

求解逆元

费马小定理:

可得

变形

对比逆元定义

可得

接下来使用快速幂算法就可以得到结果了

KMP算法

发表于 2018-12-05
字数统计: 297 | 阅读时长 ≈ 1

先存代码以后填坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;


void getNEXT(const string &s,int *NEXT) //改进后
{
NEXT[0] = -1;
int j = 0,k = -1;
while(j < s.size()-1)
{

if (k == -1 || s[j] == s[k])
{

if (s[++j] == s[++k])
NEXT[j] = NEXT[k];
else
NEXT[j] = k;
}
else
k = NEXT[k];
}
}

void getnext(const string &s,int *next) //未改进
{
next[0] = -1;
int j = 0,k = -1;
while (j < s.size()-1)
{
if (k == -1 || s[j] == s[k])
next[++j]=++k;
else
k = next[k];
}
}




int KMP(string &ob,string &pat) //返回第一次匹配成功的角标
{
int obsize=ob.size();
int patsize=pat.size();
int *next=new int[patsize];
getnext(pat,next);
int i=0,j=0;
while(i<obsize&&j<patsize&&obsize-i>=patsize-j)
{
if(j==-1 || ob[i]==pat[j])
{i++;j++;}
else
{j=next[j];}
}
delete []next;
if(j==patsize)
return i-j;
else
return -1;
}
int main()
{
while(true){
string s;
cin >> s;
int *NEXT=new int[s.size()];
int *next=new int[s.size()];
getNEXT(s,NEXT);
getnext(s,next);
for(int i=0;i<s.size();i++)
cout<<next[i]<<' ';
cout<<endl;
for(int i=0;i<s.size();i++)
cout<<NEXT[i]<<' ';
cout<<endl;
string ss;
cin>>ss;
cout<<KMP(ss,s)<<endl;
}
system("pause");
return 0;
}



//abcaabbabcabaacbacba

整数拆分

发表于 2018-11-11
字数统计: 122 | 阅读时长 ≈ 1

SHUOJ122整数拆分

​ 直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int Max=121;
int dp[Max][Max]={0};
int main()
{
for(int i=1;i<=120;++i)
for(int j=1;j<=i;++j)
{
if(i==1||j==1)
dp[i][j]=1;
else
{
if(i==j)
dp[i][j]=1+dp[i][j-1];
else if((i-j)<j)
dp[i][j]=dp[i-j][i-j]+dp[i][j-1];
else
dp[i][j]=dp[i-j][j]+dp[i][j-1];
}

}
int n;
while(scanf("%d",&n)!=EOF)
printf("%d\n",dp[n][n]);
return 0;
}

快速幂运算

发表于 2018-10-27
字数统计: 206 | 阅读时长 ≈ 1

快速幂是O(logN)的简单算法

​ 直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;

//取模运算对于加法和乘法不会改变尾数的值
//这里主要是为了防止爆精度
//快速幂复杂度是O(logN)

ll qpow(ll num,ll pow)
{
ll ret=1;
if(pow==0) return ret;
while(pow)
{
if(pow&1) ret=(ret*num)%INF;
//如果出现了对应的幂次,则乘到结果中去;
//举个例子5^6;6=110二进制;故5^6=[5^(2^2)]*(5^2);而没有5^(2^0)
num=(num*num)%INF;
//第一次为5;第二次为5^2;第三次为5^3
pow=pow>>1;
//幂次右移运算
}
return ret;
}
int main()
{
ll n,i;
while(cin>>n>>i)
cout<<qpow(n%INF,i)<<endl;
system("pause");
return 0;
}

Hexo+Github静态网页博客搭建

发表于 2018-10-12
字数统计: 1.7k | 阅读时长 ≈ 6

前置环境

1.Git
2.node.js

安装hexo并初始化

创建一个文件夹hexo,在其中右键进入 Git Bash

1
2
3
4
5
$ npm install hexo-cli -g
$ hexo init hexo
$ cd hexo
$ npm install
$ hexo server

hexo文件夹是本地网站开发环境文件夹

此时hexo文件夹目录如下

1
2
3
4
5
6
7
8
.
├── _config.yml
├── package.json
├── scaffolds
├── source
| ├── _drafts
| └── _posts
└── themes

scaffolds

模版文件夹。当您新建文章时,Hexo 会根据 scaffold 来建立文件。

Hexo的模板是指在新建的markdown文件中默认填充的内容。例如,如果您修改scaffold/post.md中的Front-matter内容,那么每次新建一篇文章时都会包含这个修改。

source

资源文件夹是存放用户资源的地方。除 _posts 文件夹之外,开头命名为 _ (下划线)的文件 / 文件夹和隐藏的文件将会被忽略。Markdown 和 HTML 文件会被解析并放到 public 文件夹,而其他文件会被拷贝过去。

themes

主题 文件夹。Hexo 会根据主题来生成静态页面。

修改网站配置

hexo/_config.yml 是我们的网站配置文件

您可以在 _config.yml 中修改大部份的配置。

网站

参数 描述
title 网站标题
subtitle 网站副标题
description 网站描述
author 您的名字
language 网站使用的语言,简体汉字使用 zh-Hans
timezone 网站时区。Hexo 默认使用您电脑的时区。时区列表。比如说:America/New_York, Japan, 和 UTC 。

其中,description主要用于SEO,告诉搜索引擎一个关于您站点的简单描述,通常建议在其中包含您网站的关键词。author参数用于主题显示文章的作者。

网址

参数 描述 默认值
url 网址
root 网站根目录
permalink 文章的 永久链接 格式 :year/:month/:day/:title/
permalink_defaults 永久链接中各部分的默认值

网站存放在子目录

如果您的网站存放在子目录中,例如 http://yoursite.com/blog,则请将您的 url 设为 http://yoursite.com/blog 并把 root 设为 /blog/。

扩展

参数 描述
theme 当前主题名称。值为false时禁用主题
deploy 部署部分的设置

详细内容请参考hexo文档

安装主题

本博客选择的是next主题

你可以在hexo主题页面找到更多主题,设置主题的方法大同小异

1
2
$ cd hexo
$ git clone https://github.com/theme-next/hexo-theme-next themes/next

此时打开hexo/themes,可以发现除了hexo默认的landscape主题以外,还多了一个主题文件夹next,打开这个文件夹,有一个文件_config.yml,这是next主题配置文件,

修改hexo/_config.yml文件,找到 theme 标签,将其值修改为 next

1
theme: next

现在可以删除landscape文件夹了

本地试运行网站

在hexo文件夹下进入 Git Bash

1
$ hexo s --debug

运行完成后打开http://localhost:4000/

配置主题

编辑 hexo/themes/next/_config.yml

主题样式 Scheme 标签

Scheme 是 next 提供的一种特性,借助于 Scheme,next 为你提供多种不同的外观。同时,几乎所有的配置都可以 在 Scheme 之间共用。目前 next 支持三种 Scheme,他们是:

Muse - 默认 Scheme,这是 NexT 最初的版本,黑白主调,大量留白
Mist - Muse 的紧凑版本,整洁有序的单栏外观
Pisces - 双栏 Scheme,小家碧玉似的清新
Gemini - 左侧网站信息及目录,块+片段结构布局 

Scheme 的切换通过更改主题配置文件,搜索 scheme 关键字。 你会看到有四行 scheme 的配置,将你需用启用的 scheme 前面注释 # 去除即可。

菜单 Menu标签

1
2
3
4
5
6
7
8
menu:   
home: / || home //首页
archives: /archives/ || archive //归档
categories: /categories/ || th //分类
tags: /tags/ || tags //标签
about: /about/ || user //关于
#schedule: /schedule/ || calendar //日程表
#sitemap: /sitemap.xml || sitemap //站点地图 #commonweal: /404/ || heartbeat //公益404

看看你需要哪个菜单就把哪个取消注释打开就行了

||之后的archive表示图标,Next主题所有的图标都来自Font Awesome图标库。

侧栏sidebar标签

sidebar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#Sidebar Position - 侧栏位置(只对Pisces | Gemini两种风格有效)

position: left //靠左放置
#position: right //靠右放置

#Sidebar Display - 侧栏显示时机(只对Muse | Mist两种风格有效)
#display: post //默认行为,在文章页面(拥有目录列表)时显示
display: always //在所有页面中都显示
#display: hide //在所有页面中都隐藏(可以手动展开)
#display: remove //完全移除

offset: 12 //文章间距(只对Pisces | Gemini两种风格有效)
b2t: false //返回顶部按钮(只对Pisces | Gemini两种风格有效)
scrollpercent: true //返回顶部按钮的百分比

头像 avatar标签

1
2
# Sidebar Avatar
avatar: /images/avatar.jpg

将你的头像命名为avatar.jpg放入themes/next/source/images(没有请创建)中

更多配置请参考 next官方文档

以及万能的百度

生成及部署

进入hexo文件夹并打开Git Bash

1
2
$ cd hexo
$ hexo generate

或者简写为

1
$ hexo g

此时将生成静态文件夹 hexo/public

将这个文件夹 git push 到你的Github下的 username.github.io repo(没有请新建),其中 username 是你的Github用户名

然后打开网址username.github.io

即可看到你的博客

或者使用git进行部署

修改hexo/_config.yml 中的deploy标签

1
2
3
4
5
> deploy:
> type: git
> repo: git@github.com:username/username.github.io.git
> branch: master
>

>

安装 hexo-deployer-git

1
2
> $ npm install hexo-deployer-git --save
>

>

生成

1
2
> $ hexo generate
>

>

部署

1
2
> $ hexo deploy
>

>

或者

您可执行下列的其中一个命令,让 Hexo 在生成完毕后自动部署网站,两个命令的作用是相同的。

1
2
3
> $ hexo generate --deploy
> $ hexo deploy --generate
>

>

简写

上面两个命令可以简写为

1
2
3
> $ hexo g -d
> $ hexo d -g
>

写作

hexo写作使用Markdown格式(本文也是)

Markdown格式文件后缀一般为.md

Markdown 是一种轻量级的「标记语言」,它的优点很多,目前也被越来越多的写作爱好者,撰稿者广泛使用。看到这里请不要被「标记」、「语言」所迷惑,Markdown 的语法十分简单。常用的标记符号也不超过十个,这种相对于更为复杂的 HTML 标记语言来说,Markdown 可谓是十分轻量的,学习成本也不需要太多,且一旦熟悉这种语法规则,会有一劳永逸的效果。

这里推荐一个非常好用的markdown编辑器 typora

请在每个 .md文件开头加入标题格式

1
2
3
---
title: yourtitle
---

将写好的 .md 文件放入/hexo/source/_posts重新生成部署即可

注意:_posts文件夹是博文存储目录

==呼,写完了==

以后可能还会更新更多新东西

12
ferryvan

ferryvan

1+1==2

12 日志
GitHub E-Mail 503OJ(弃用)
友情链接
  • compute
  • Lin
  • longfangsong
  • zhoudian64
© 2019 ferryvan | Site words total count: 9k
访客: