kk Blog —— 通用基础


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

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一样

https://cloud.tencent.com/document/product/400/35244

vim /etc/nginx/nginx.conf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

http {
	server {
		listen  443;
		server_name test.com;
		ssl on;
		# ssl_certificate /root/test.crt;
		# ssl_certificate_key /root/test_private.perm;
		ssl_certificate /root/kk/www.npcable.cn_nginx/www.npcable.cn_bundle.crt;
		ssl_certificate_key /root/kk/www.npcable.cn_nginx/www.npcable.cn.key;
		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;
	}
};

逆元

https://blog.csdn.net/baidu_35643793/article/details/75268911

1.什么是逆元

当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：

设c是b的逆元，则有b*c≡1(mod m)；

则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);

即a/b的模等于a*b的逆元的模；

逆元就是这样应用的；

2.求逆元的方法

(1).费马小定理

在是素数的情况下，对任意整数都有。 如果无法被整除，则有。 可以在为素数的情况下求出一个数的逆元，，即为逆元。

题目中的数据范围1<=x<=109，p=1000000007，p是素数；

所以x肯定就无法被p整除啊，所以最后就得出xp-2为x的逆元啦。

复杂度O(logn)；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const int mod = 1000000009;  
long long quickpow(long long a, long long b) {  
	if (b < 0) return 0;  
	long long ret = 1;  
	a %= mod;  
	while(b) {  
		if (b & 1) ret = (ret * a) % mod;  
		b >>= 1;  
		a = (a * a) % mod;  
	}  
	return ret;  
}  
long long inv(long long a) {  
	return quickpow(a, mod - 2);  
}

(2)扩展欧几里得算法求逆元

可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；

复杂度：O(logn)；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ll extend_gcd(ll a, ll b, ll &x, ll &y) {  
	if (b == 0) {  
		x = 1, y = 0;  
		return a;  
	}  
	else {  
		ll r = extend_gcd(b, a % b, y, x);  
		y -= x * (a / b);  
		return r;  
	}  
}  
ll inv(ll a, ll n) {  
	ll x, y;  
	extend_gcd(a, n, x, y);  
	x = (x % n + n) % n;  
	return x;  
}

(3) 逆元线性筛 ( P为质数 )

求1,2,…,N关于P的逆元（P为质数）

复杂度：O(N)

代码：

1
2
3
4
5
6

const int mod = 1000000009;  
const int maxn = 10005;  
int inv[maxn];  
inv[1] = 1;  
for(int i = 2; i < 10000; i++)  
	inv[i] = inv[mod % i] * (mod - mod / i) % mod;