发表于
字数统计: 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

此时有

求解逆元

费马小定理：

可得

变形

对比逆元定义

可得

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

发表于
字数统计: 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

发表于
字数统计: 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;
}

发表于
字数统计: 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;
}

发表于
字数统计: 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文件夹是博文存储目录

==呼，写完了==

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