kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

nginx 四层转发配置

nginx rpm: http://nginx.org/packages/mainline/centos/7/x86_64/RPMS/

nginx source: http://nginx.org/en/download.html

nginx stream: http://nginx.org/en/docs/stream/ngx_stream_core_module.html

http://www.52devops.com/chuck/1153.html

一、nginx四层代理

Nginx 1.9.0 开发版发布,该版本增加了 stream module 用于一般的 TCP 代理和负载均衡。

三、nginx四层代理实战

3.1编译安装nginx

编译安装nginx需指定–with-stream参数

1
2
[root@linux-node1 nginx-1.9.12]#./configure --prefix=/usr/local/nginx-1.9.12 --user=www --group=www --with-http_ssl_module --with-http_stub_status_module --with-file-aio --with-stream
[root@linux-node1 nginx-1.9.12]#make && make install
3.2 使用nginx实现ssh四层代理

编辑nginx配置文件并启动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[root@linux-node1 conf]# vim nginx.conf
worker_processes  1;
events {
    worker_connections  1024;
}
stream {  #类似于7层的http段
    upstream ssh_proxy {
        hash $remote_addr consistent;
        server 192.168.56.11:22;
        server 192.168.56.12:22;
    }
    server {
        listen 2222;
        proxy_connect_timeout 1s;
        proxy_timeout 300s;
        proxy_pass ssh_proxy;
    }
}
[root@linux-node1 conf]# ../sbin/nginx
[root@linux-node1 conf]# netstat -lntup|grep nginx
tcp        0      0 0.0.0.0:2222            0.0.0.0:*               LISTEN      61127/nginx: master

连接ssh,从结果看把请求抛向了linux-node2的ssh

1
2
3
4
[root@linux-node1 conf]# ssh -p 2222 root@192.168.56.11
root@192.168.56.11's password:
Last login: Sun Mar  6 17:29:42 2016 from linux-node1.example.com
[root@linux-node2 ~]# Connection to 192.168.56.11 closed by remote host.

lvs fwmark 模式

http://blog.51cto.com/angus717/769577

persistent netfilter marked packet persistence 持久防火墙标记(在pre-routing链上打netfilter marked,而且该标记只在防火墙内部有效通常是0-99)

1
2
3
4
5
6
7
8
9
10
11
12
13
[root@slave ~]# ipvsadm -C
[root@slave ~]# iptables -t mangle -A PREROUTING -i eth0 -p tcp -d 172.16.8.120 --dport 80 -j MARK --set-mark 80
[root@slave ~]# iptables -t mangle -A PREROUTING -i eth0 -p tcp -d 172.16.8.120 --dport 443 -j MARK --set-mark 80
[root@slave ~]# ipvsadm -A -f 80 -s rr -p 1000
[root@slave ~]# ipvsadm -a -f 80 -r 172.16.100.7 -g
[root@slave ~]# ipvsadm -a -f 80 -r 172.16.100.6 -g
[root@slave ~]# ipvsadm -Ln
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
  -> RemoteAddress:Port           Forward Weight ActiveConn InActConn
FWM  80 rr persistent 1000
  -> 172.16.100.6:0               Route   1      0          0        
  -> 172.16.100.7:0               Route   1      0          0 

nginx https/nginx 配置

curl wget 不验证证书进行https请求

1
2
wget 'https://x.x.x.x/get_ips' --no-check-certificate
curl 'https://x.x.x.x/get_ips' -k

服务端

生成证书和私匙

1
openssl req -newkey rsa:4096 -nodes -keyout test_private.perm -new -x509 -sha512 -days 3650 -subj "/CN=test.com/" -out test.crt

test_private.perm 是私匙, test.crt 是证书

其中CN和nginx.conf中的server_name一样

vim /etc/nginx/nginx.conf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
http {
	server {
		listen  443;
		server_name test.com;
		ssl on;
		ssl_certificate /root/test.crt;
		ssl_certificate_key /root/test_private.perm;
		location / {
			root /var/www/html;
			index index.html;
		}
	}
	...
}

客户端

自建证书得不到信任,所以会提示: curl: (60) Peer’s certificate issuer has been marked as not trusted by the user.

解决方法:

拿服务器证书

1
openssl s_client -showcerts -connect www.baidu.com:443

curl 参数带证书

1
curl -v 'https://test.com/kk' --resolve 'test.com:443:192.168.2.7' --trace-time --cacert /root/test.crt

或者将证书加到信任的证书列表中

1
2
cat /root/test.crt >> /etc/pki/ca-trust/extracted/pem/tls-ca-bundle.pem
curl -v 'https://test.com/kk' --resolve 'test.com:443:192.168.2.7' --trace-time

访问的host一定要是证书中CN(commonname), 不然会提示: curl: (51) Unable to communicate securely with peer: requested domain name does not match the server’s certificate.

git tag常用操作

https://blog.csdn.net/albertsh/article/details/63253614

用途

标签可以针对某一时间点的版本做标记,常用于版本发布,这恰恰是我所需要的功能,将本地标签推送到Github上即发布了一个Release版本,下载和查看非常方便。

标签分类

git标签分为两种类型:轻量标签和附注标签。轻量标签是指向提交对象的引用,附注标签则是仓库中的一个独立对象,建议使用附注标签,日后还可以查看标签信息。

创建标签

创建轻量标签

1
$ git tag v0.2.0 -light

解释:创建轻量标签不需要传递参数,直接指定标签名称即可。

创建附注标签

1
$ git tag -a v0.1.0 -m "release 0.1.0 version"

解释:创建附注标签时,参数-a即annotated的缩写,指定标签类型,后附标签名。参数m指定标签说明,说明信息会保存在标签对象中。

查看标签

列出当前仓库的所有标签

1
$ git tag

列出符合模式的标签

1
$ git tag -l 'v0.1.*'

查看标签版本信息

1
$ git show v0.1.0

切换标签

切换标签与切换分支命令相同

1
$ git checkout [tagname]

解释:切换标签后处于一个空的分支上,即”You are in ‘detached HEAD’ state.”

删除标签

误打或需要修改标签时,需要先将标签删除,再打新标签

1
$ git tag -d v0.1.2

解释:参数-d即delete的缩写,意为删除其后指定的标签。

补打标签

给指定的commit打标签

1
$ git tag -a v0.1.0 49e0cd22f6bd9510fe65084e023d9c4316b446a6

解释:打标签不必要在HEAD之上,也可在之前的版本上打,这需要你知道某个提交对象的校验和,通过git log命令获取。

发布标签

将v0.1.0标签提交到git服务器

1
$ git push origin v0.1.0

解释:通常的git push不会将标签对象提交到git服务器,我们需要进行显式的操作。

将本地所有标签一次性提交到git服务器

1
$ git push origin –tags

生成树计数

http://blog.sina.com.cn/s/blog_a55522150102w6sp.html http://www.xuebuyuan.com/1622347.html

基尔霍夫定理

算法思想:

1
2
3
4
5
6
7
8
9
10
*(1)G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0;当i=j时,dij等于vi的度数; 
*(2)G的邻接矩阵A[G]是一个n*n的矩阵,并且满足:如果vi,vj之间有边直接相连,则aij=1,否则为0; 
*定义图G的Kirchhoff矩阵C[G]为C[G]=D[G]-A[G]; 
*Matrix-Tree定理:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值; 
*所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行,第r列同时去掉后得到的新矩阵,用Cr[G]表示; 
* 
*Kirchhoff矩阵的特殊性质: 
*(1)对于任何一个图G,它的Kirchhoff矩阵C的行列式总是0,这是因为C每行每列所有元素的和均为0; 
*(2)如果G是不连通的,则它的Kirchhoff矩阵C的任一个主子式的行列式均为0; 
*(3)如果G是一颗树,那么它的Kirchhoff矩阵C的任一个n-1阶主子式的行列式均为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
87
88
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define  zero(x) (((x)>0?(x):(-x))<1e-15)
using namespace std;
const int MAXN = 110;
double a[MAXN][MAXN], b[MAXN][MAXN];
int G[MAXN][MAXN];
int N, M;

/*
*生成树计数
*1、G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0;当i=j时,dij等于vi的度数。
*2、G的邻接矩阵A[G]也是一个n*n的矩阵, 并且满足:如果vi、vj之间有边直接相连,则aij=1,否则为0。
*我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:
*G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。
*所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行、第r列同时去掉后得到的新矩阵,用Cr[G]表示。
*/

double Det(double a[MAXN][MAXN], int n)
{
	int i, j, k, sign = 0;
	double ret = 1, t;
	for(i = 0; i < n; ++i)
		for(j = 0; j < n; ++j)
			b[i][j] = a[i][j];
	for(i = 0; i < n; ++i)
	{
		if(zero(b[i][i]))
		{
			for(j = i + 1; j < n; ++j)
			{
				if(!zero(b[j][i]))
					break;
			}
			if(j == n)
				return 0;
			for(k = i; k < n; ++k)
				t = b[i][k], b[i][k] = b[j][k], b[j][k] = t;
			sign++;
		}
		ret *= b[i][i];
		for(k = i + 1; k < n; ++k)
			b[i][k] /= b[i][i];
		for(j = i + 1; j < n; ++j)
			for(k = i + 1; k < n; ++k)
				b[j][k] -= b[j][i] * b[i][k];
	}
	if(sign & 1)
		ret = - ret;
	return ret;
}

int main()
{
	int T, u, v;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &N, &M);
		memset(G, 0, sizeof(G));
		memset(a, 0, sizeof(a));
		while(M--)
		{
			scanf("%d %d", &u, &v);
			G[u-1][v-1] = G[v-1][u-1] = 1;
		}
		for(int i = 0; i < N; ++i)
		{
		   int d = 0;
		   for (int j = 0; j < N; ++j) if(G[i][j]) d++;
		   a[i][i] = d;
		}
		for(int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (G[i][j]) a[i][j] = -1;
			}
		}
	   double ans = Det(a, N - 1);
	   printf("%0.0lf\n", ans);
	}
	return 0;
}

SRM733-DIV1-B

https://community.topcoder.com/stat?c=round_stats&rd=17140&dn=1

Problem Statement

     Consider an undirected, complete, simple graph G on n vertices. The vertices of G are labeled from 1 to n. Specifically, each pair of distinct vertices is connected by a single undirected edge, so there are precisely n*(n-1)/2 edges in this graph.

You are given a set E that contains some edges of the graph G. More precisely, you are given the vector s x and y. For each valid i, (x[i], y[i]) is one of the edges in E.

A spanning tree of G is a subset of exactly n-1 edges of G such that the edges connect all n vertices. You may note that the edges of a spanning tree do indeed form a tree that is a subgraph of G and spans all its vertices.

We are interested in spanning trees that contain all of the edges in the provided set E. Compute and return the number of such spanning trees modulo 987,654,323. Two spanning trees are different if there is an edge of G that is in one of them but not in the other. Definition     

Class:

BuildingSpanningTreesDiv1

Method:

getNumberOfSpanningTrees

Parameters:

int, vector , vector

Returns:

int

Method signature:

int getNumberOfSpanningTrees(int n, vector x, vector y)

(be sure your method is public)

Limits

Time limit (s): 2.000

Memory limit (MB): 256

Notes

987,654,323 is a prime number.

Constraints

n will be between 1 and 1,000, inclusive.
x will contain between 1 and 1,000 elements, inclusive.
y will contain between 1 and 1,000 elements, inclusive.
x and y will contain the same number of elements.
Each element of x will be between 1 and n-1, inclusive.
Each element of y will be between 2 and n, inclusive.
For each valid i, x[i] will be less than y[i].
All edges in E will be distinct.

Examples

0)
3
{1,2}
{2,3}
Returns: 1
The edges in the provided set E alredy form a spanning tree, so there is exactly one spanning tree that contains them.

1)
5
{1,3,4}
{2,4,5}
Returns: 6
There are six ways to add the one missing edge: one endpoint of the new edge must lie in the set {1,2} and the other in the set {3,4,5}.

2)
4
{1}
{2}
Returns: 8
There are eight spanning trees that contain the edge (1, 2):
{(1, 2), (1, 3), (1, 4)}
{(1, 2), (1, 3), (2, 4)}
{(1, 2), (1, 3), (3, 4)}
{(1, 2), (2, 3), (2, 4)}
{(1, 2), (1, 4), (2, 3)}
{(1, 2), (1, 4), (3, 4)}
{(1, 2), (2, 3), (3, 4)}
{(1, 2), (2, 4), (3, 4)}

3)
4
{1,2,1}
{2,3,3}
Returns: 0
The set E contains a cycle, and thus there is no spanning tree that contains all these edges.

4)
8
{1,4,2,3,5}
{4,7,6,5,8}
Returns: 144

5)
1000
{1}
{2}
Returns: 529013784

Don’t forget to take the modulo.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. ©2003, TopCoder, Inc. All rights reserved.

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdint.h>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
int const MAX_N = 1003;
int const MOD = 987654323;
 
int p [MAX_N];
int s [MAX_N];
 
int root (int v)
{
	if (p[v] != v)
	{
		p[v] = root (p[v]);
	}
	return p[v];
}
 
bool unite (int u, int v)
{
	u = root (u);
	v = root (v);
	if (u == v)
	{
		return false;
	}
	p[v] = u;
	s[u] += s[v];
	return true;
}
 
int powmod (int a, int b)
{
	int res = 1;
	for ( ; b > 0; b >>= 1)
	{
		if (b & 1)
		{
			res = (res * 1LL * a) % MOD;
		}
		a = (a * 1LL * a) % MOD;
	}
	return res;
}
 
int a [MAX_N] [MAX_N];
int n;
 
int det (void)
{
	int res = 1;
	for (int i = 1; i < n; i++)
	{
		int j;
		for (j = i; j < n; j++)
		{
			if (a[j][i])
			{
				break;
			}
		}
		if (j == n)
		{
			return 0;
		}
		if (j != i)
		{
			for (int k = i; k < n; k++)
			{
				swap (a[i][k], a[j][k]);
			}
		}
		res = (res * 1LL * a[i][i]) % MOD;
		int inv = powmod (a[i][i], MOD - 2);
		for (int j = i + 1; j < n; j++)
		{
			int mult = (a[j][i] * 1LL * inv) % MOD;
			for (int k = i; k < n; k++)
			{
				a[j][k] = (a[j][k] -
						a[i][k] * 1LL * mult) % MOD;
			}
		}
	}
	return (res + MOD) % MOD;
}
 
class BuildingSpanningTreesDiv1
{
public:
	int getNumberOfSpanningTrees (int n, vector <int> x, vector <int> y)
	{
		for (int i = 0; i < n; i++)
		{
			p[i] = i;
			s[i] = 1;
		}
		int k = (int) (x.size ());
		for (int w = 0; w < k; w++)
		{
			int u = x[w] - 1;
			int v = y[w] - 1;
			if (!unite (u, v))
			{
				return 0;
			}
			a[u][v] += 1;
			a[v][u] += 1;
			a[u][u] -= 1;
			a[v][v] -= 1;
		}
 
		int t = 0;
		for (int i = 0; i < n; i++)
		{
			if (p[i] == i)
			{
				s[t] = s[i];
				t += 1;
			}
		}
 
		n -= k;
		::n = n;
 
		memset (a, 0, sizeof (a));
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				int e = s[i] * s[j];
				a[i][j] -= e;
				a[j][i] -= e;
				a[i][i] = (a[i][i] + e) % MOD;
				a[j][j] = (a[j][j] + e) % MOD;
			}
		}
 
		int res = det ();
		return res;
	}
};