Codeforces Template
VIM
1syntax on
2set cindent
3set nu
4set tabstop=4
5set shiftwidth=4
6set background=dark
7
8map <C-A> ggVG"+y
9map <F5> :call Run()<CR>
10func! Run()
11 exec "w"
12 exec "!g++ -Wall % -o %<"
13 exec "!./%<"
14endfunc
1#!/bin/bash
2
3for name in {A..M};
4do
5 cp a.cpp $name.cpp
6done
1filetype plugin indent on
2colorscheme desert
3syntax on
4set nu
5set backspace=2
6set hlsearch
7set syntax=on
8set tabstop=4
9set shiftwidth=4
10set smarttab
11set smartindent
12set showmatch
13set matchtime=0
14set report=0
15:inoremap ( ()<ESC>i
16:inoremap [ []<ESC>i
17:inoremap { {}<ESC>i
18:inoremap {<CR> {<CR>}<ESC>O
19:inoremap ) <c-r>=Close(')')<CR>
20:inoremap ] <c-r>=Close(']')<CR>
21:inoremap } <c-r>=Close('}')<CR>
22function Close(char)
23 if getline('.')[col('.') - 1] == a:char
24 return "\<Right>"
25 else
26 return a:char
27 endif
28endfunction
29
30map <C-A> ggVG"+y
31map <F5> :call Run()<CR>
32func! Run()
33 exec "w"
34 exec "!g++-7 -O2 -std=c++11 -Wall % -o %<"
35 exec "!./%<"
36endfunc
37
38map <F12> :call SetTitle()<CR>
39func SetTitle()
40let l = 0
41let l = l + 1 | call setline(l,'/* ***********************************************')
42let l = l + 1 | call setline(l,'Author : Akvicor')
43let l = l + 1 | call setline(l,'Created Time : '.strftime('%c'))
44let l = l + 1 | call setline(l,'File Name : '.expand('%'))
45let l = l + 1 | call setline(l,'************************************************ */')
46let l = l + 1 | call setline(l,'')
47
48let l = l + 1 | call setline(l,'#include <bits/stdc++.h>')
49let l = l + 1 | call setline(l,'')
50let l = l + 1 | call setline(l,'#define FAST_IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);')
51let l = l + 1 | call setline(l,'')
52let l = l + 1 | call setline(l,'using namespace std;')
53let l = l + 1 | call setline(l,'')
54let l = l + 1 | call setline(l,'int main(){')
55let l = l + 1 | call setline(l,' FAST_IO;')
56let l = l + 1 | call setline(l,' ')
57let l = l + 1 | call setline(l,' return 0;')
58let l = l + 1 | call setline(l,'}')
59endfunc
快速幂
1LL quick_pow(LL a, LL b, LL p) {
2 LL res = 1 % p;
3 for (; b; b >>= 1) {
4 if (b & 1) res = res * a % p;
5 a = a * a % p;
6 }
7 return res;
8}
快速乘
1// O(1)
2ll mul(ll a, ll b, ll p) {
3 return ((__int128)a*b)%p;
4}
5// O(1)
6ll mul(ll a, ll b, ll p) {
7 a %= p; b %= p;
8 ll c = (long double)a * b / p;
9 ll ans = a * b - c * p;
10 return (ans % p + p) % p;
11}
12// O(log)
13ll mul(ll a, ll b, ll p) {
14 ll ans = 0;
15 while (b) {
16 if (b & 1) ans = (ans + a) % p;
17 a = a * 2 % p;
18 b >>= 1;
19 }
20 return ans;
21}
欧拉φ函数
1int GetEuler(int n) { //欧拉函数
2 int res = n;
3 for(int i = 2;i*i <= n; ++i){
4 if(a%i == 0){
5 res -= res/i;
6 while(n%i == 0)
7 n /= i;
8 }
9 }
10 if(a > 1) // 因为是遍历到sqrt(n)，所以可能存在未除尽或者n本身就为质数的情况
11 res -= res/n;
12 return res;
13}
14
15int Phi(int x) { //欧拉函数
16 int i, re = x;
17 for (i = 2; i * i <= x; i++)
18 if (x % i == 0) {
19 re /= i;
20 re *= i - 1;
21 while (x % i == 0)
22 x /= i;
23 }
24 if (x ^ 1) re /= x, re *= x - 1;
25 return re;
26}
欧拉函数线性筛
1const int MAXN = 1e6;
2//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
3int tot;
4int phi[MAXN]; //保存各个数字的欧拉函数
5int prime[MAXN]; //按顺序保存素数
6bool mark[MAXN]; //判断是否是素数
7void get_phi(int N){
8 phi[1] = 1;
9 for(int i = 2; i <= MAXN; i++){ //相当于分解质因数的逆过程
10 if(!mark[i]){
11 prime[++tot] = i;
12 phi[i] = i-1;
13 }
14 for(int j = 1; j <= tot; j++){
15 if(i * prime[j] > N) break;
16 mark[i * prime[j]] = 1; //确定i*prime[j]不是素数
17 if(i % prime[j] == 0){ //判断prime[j] 是否为 i的约数
18 phi[i * prime[j]] = phi[i] * prime[j];
19 break;
20 }
21 else{ //prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性
22 phi[i * prime[j]] = phi[i] * (prime[j] - 1);
23 }
24 }
25 }
26}
Green公式-判断多边形边界曲线顺/逆时针
1double d = 0;
2for (int i = 0; i < n - 1; i++) {
3 d += -0.5 * ( y[i + 1] + y[i]) * (x[i + 1] - x[i]);
4}
5if ( d > 0)
6 cout << "counter clockwise" << endl;
7else
8 cout << "clockwise" << endl;
dijkstra
1const int INF = 0x3f3f3f3f;
2#define maxn 1000+100
3int path[maxn][maxn], dis[maxn]; // 地图 起点到达i的距离
4bool vis[maxn]; // 是否访问过
5int n, t; // 地标数 路径数
6
7void init() {
8 for (int i = 0; i < maxn; ++i) {
9 for (int j = 0; j < maxn; ++j) {
10 path[i][j] = INF;
11 }
12 path[i][i] = 0;
13 }
14}
15
16void dijkstra(){
17 // 将1到i的距离初始化
18 for (int i = 1; i <= n; i++) {
19 dis[i] = path[1][i];
20 vis[i] = false;
21 }
22 vis[1] = true; // 标记起点为访问过的
23 dis[1] = 0; // 起点到起点的距离为0
24 for (int i = 2; i <= n; i++) { // 从2号节点遍历到n号节点
25 int now = -1, minL = INF;
26 // 遍历一遍dis数组，寻找到未访问过的到1最短的路径长度
27 for (int j = 1; j <= n; j++) { // 从1到n
28 if (!vis[j] && minL > dis[j]) { // 如果没有访问过当前节点，并且当前从1到j的距离小于最大长度
29 now = j; // 更新最短路径的位置
30 minL = dis[j]; // 最短距离等于当前
31 }
32 }
33 if (now == -1) break; // 未找到
34 vis[now] = true; // 将now标记为访问过
35 // 从1开始寻找到j最短的路径
36 for (int j = 1; j <= n; j++) {
37 // 没有访问过 并且当前已走的长度加上走到j节点的长度小于当前dis[j]
38 if (!vis[j] && (dis[now] + path[now][j]) < dis[j]) {
39 dis[j] = dis[now] + path[now][j]; // 更新从起点到j的最短路径
40 }
41 }
42 }
43}
44
45int main() {
46 freopen("in.txt", "r", stdin); // 从指定文件输入数据 提交时注释掉
47// memset(path, INT_MAX, sizeof(path));
48 while (scanf("%d %d", &n, &t) != EOF) {
49 init();
50 for (int i = 0; i < t; i++) {
51 int from, to, len;
52 scanf("%d %d %d", &from, &to, &len);
53 if (path[from][to] > len)
54 path[from][to] = path[to][from] = len;
55 }
56 dijkstra();
57 for (int i = 1; i <= n; i++) {
58 printf("1 to %d min= %d\n", i, dis[i]);
59 }
60 }
61 return 0;
62}
素性测试
1bool is_prime(int n){ /* 判定一个数是不是素数 ，假设输入的数都是正整数 */
2 for (int i = 2; i * i <= n; i++) {
3 if (!(n % i)) return false;
4 }
5 return n != 1; /* 1是例外 */
6}
7
8
9const int S = 8;
10
11LL mult_mod(LL a, LL b, LL c){
12 a %= c;
13 b %= c;
14 LL ret = 0;
15 LL tmp = a;
16 while(b){
17 if(b&1){
18 ret += tmp;
19 if(ret > c) ret -= c;
20 }
21 tmp <<= 1;
22 if(tmp > c) tmp -= c;
23 b >>= 1;
24 }
25 return ret;
26}
27
28LL pow_mod(LL a, LL n, LL mod){
29 LL ret = 1;
30 LL temp = a % mod;
31 while(n){
32 if(n & 1) ret = mult_mod(ret, temp, mod);
33 temp = mult_mod(temp, temp, mod);
34 n >>= 1;
35 }
36 return ret;
37}
38
39bool check(LL a, LL n, LL x, LL t){
40 LL ret = pow_mod(a, x, n);
41 LL last = ret;
42 loop(i, 1, t){
43 ret = mult_mod(ret, ret, n);
44 if(ret == 1 && last != 1 && last != n-1) return true;
45 last = ret;
46 }
47 if(ret != 1) return true;
48 else return false;
49}
50
51bool Miller_Rabin(LL n){
52 if(n < 2) return false;
53 if(n == 2) return true;
54 if((n&1)==0) return false;
55 LL x = n-1;
56 LL t = 0;
57 while((x&1)==0){x >>= 1; ++t;}
58 srand(time(NULL));
59 rep(i, S){
60 LL a = rand()%(n-1)+1;
61 if(check(a, n, x, t)) return false;
62 }
63 return true;
64}
埃氏筛法
1bool is_prime[100];
2int prime[100];
3int sieve(int n) { /* 枚举n以内的素数 */
4 /* 返回n以内素数的个数，素数存在prime数组里 */
5 int p = 0;
6 for (int i = 0; i <= n; i++)
7 is_prime[i] = true;
8 is_prime[0] = is_prime[1] = false;
9 for (int i = 2; i <= n; i++) {
10 if (is_prime[i]) {
11 prime[p++] = i;
12 for (int j = i * 2; j <= n; j += i)
13 is_prime[j] = false;
14 }
15 }
16 return p;
17}
区间筛法
1#define M 100000000
2typedef long long ll;
3bool is_prime_small[M];
4bool is_prime[M];
5ll ans = 0;
6
7void prime(ll a, ll b) {
8 for (ll i = 2; i * i < b; i++) is_prime_small[i] = true; //初始化2~b^(1/2)
9 for (ll i = 0; i < b - a; i++) is_prime[i] = true; //因为a,b很大，所以用0~b-a 代表a~b
10 for (ll i = 2; i * i < b; i++) {
11 if (is_prime_small[i]) {
12 for (ll j = 2 * i; j * j < b; j += i) is_prime_small[j] = false;
13 for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) { //找到从a开始的第一个合数
14 if (is_prime[j - a]) {
15 ans++; //求出几个合数。 //或者也可以最后遍历b-a这区间，求出质数的个数。
16 is_prime[j - a] = false;
17 }
18 }
19 }
20 }
21}
22
23int main() {
24 ll a, b;
25 ans = 0;
26 cin >> a >> b;
27 prime(a, b);
28 // for(ll i = 0;i < b-a;i++)
29 // if(is_prime[i]) ans++;
30 cout << "ans = " << b - a - ans << endl;
31 return 0;
32}
线段树
1class SegmentTree{
2
3private:
4 int * tree;
5 int N;
6
7public:
8 int * temp;
9
10 SegmentTree(unsigned int n){
11 tree = new int [(n<<2u) +10u];
12 temp = new int [(n<<2u) +10u];
13 this->N = n;
14 }
15
16 ~SegmentTree(){
17 delete[] tree;
18 delete[] temp;
19 }
20
21 /**
22 * 建树
23 */
24 void init(){
25 build(1, 1, this->N);
26 }
27
28 /**
29 * 建树
30 * @param p p树
31 * @param l 区间左端点
32 * @param r 区间右端点
33 */
34 void build(int p, int l, int r){
35 if(l == r){
36 tree[p] = temp[l];
37 return;
38 }
39 int mid = l + (r - l) / 2;
40 build(p * 2, l, mid);
41 build(p * 2 + 1, mid + 1, r);
42 tree[p] = tree[p * 2] + tree[p * 2 + 1];
43 }
44
45 /**
46 * 更新
47 * @param p 当前节点编号
48 * @param l 区间左界
49 * @param r 区间右界
50 * @param x 需要修改的节点编号
51 * @param num 操作
52 */
53 void change(int p, int l, int r, int x, int num){
54 if(l == r){
55 tree[p] += num;
56 if(tree[p]<0) tree[p] = 0;
57 return;
58 }
59 int mid = l + (r - l) / 2;
60 if(x <= mid) change(p * 2, l, mid, x, num);
61 else change(p * 2 + 1, mid + 1, r, x, num);
62 tree[p] = tree[p * 2] + tree[p * 2 + 1];
63 }
64
65
66 /**
67 * 查询
68 * @param p 在p这棵树
69 * @param l p的左区间端点
70 * @param r p的右区间端点
71 * @param x 查询区间左端点
72 * @param y 查询区间右端点
73 * @return 区间和
74 */
75 int find(int p, int l, int r, int x, int y){
76 if(x <= l && r <= y) return tree[p];
77 int mid = l + (r - l) / 2;
78 if(y <= mid) return find(p * 2, l, mid, x, y);
79 if(x > mid) return find(p * 2 + 1, mid + 1, r, x, y);
80 return find(p * 2, l, mid, x, mid) + find(p * 2 + 1, mid + 1, r, mid + 1, y);
81 }
82
83};
最大子列和问题
1int maxsequence3(int a[], int len)
2{
3 int maxsum, maxhere;
4 maxsum = maxhere = a[0]; //初始化最大和为a【0】
5 for (int i=1; i<len; i++) {
6 if (maxhere <= 0)
7 maxhere = a[i]; //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
8 else
9 maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
10 if (maxhere > maxsum) {
11 maxsum = maxhere; //更新最大连续子序列和
12 }
13 }
14 return maxsum;
15}
约数个数定理
1int f1(int n) {
2 int r = (int) sqrt(1.0 * n);
3 int sum = 0;
4 if (r * r == n) {
5 sum++;
6 r--;
7 }
8 for (int i = 1; i <= r; i++)
9 if (n % i == 0) {
10 sum += 2;
11 }
12 cout << sum << endl;
13}
14
15// 稍快于f1
16int f2(int n){
17 int s = 1, r;
18 for (int i = 2; i * i <= n; i++) {
19 r = 0;
20 while (n % i == 0) {
21 r++;
22 n /= i;
23 }
24 if (r > 0) {
25 r++;
26 s *= r;
27 }
28 }
29 if (n > 1)
30 s *= 2;
31 cout << s << endl;
32}
33
34ll f3(ll n) {
35 ll res=1;
36 for(ll i=2;i*i<=n;i++){
37 ll k=0;
38 while(n%i == 0){
39 n = n/i;
40 k++;
41 }
42 if(k) res *= (k+1);
43 }
44 if(n != 1) res=res*2;
45 if(res==1){
46 if(n==1) return 1;
47 else return 2;
48 }
49 cout << res << endl;
50}
约数和定理
1ll qpow(ll x, ll y) {
2 ll res = 1;
3 while (y) {
4 if (y & 1) res *= x;
5 x *= x;
6 y >>= 1;
7 }
8 return res;
9}
10
11ll getsum(ll n) {//返回n的约数和是多少.
12 ll res = 1;
13 for (ll i = 2; i * i <= n; i++) {
14 ll k = 0;
15 while (n % i == 0) {
16 n = n / i;
17 k++;
18 }
19 res *= ((1 - qpow(i, k + 1)) / (1 - i));
20 } //用等比数列公式(快速幂)算.
21 if (n != 1) res *= (1 + n);
22 cout << res << endl;
23}
大整数
1#include <bits/stdc++.h>
2using namespace std;
3// base and base_digits must be consistent
4constexpr int base = 1000000000;
5constexpr int base_digits = 9;
6
7struct bigint {
8 // value == 0 is represented by empty z
9 vector<int> z; // digits
10
11 // sign == 1 <==> value >= 0
12 // sign == -1 <==> value < 0
13 int sign;
14
15 bigint() : sign(1) {}
16 bigint(long long v) { *this = v; }
17
18 bigint &operator=(long long v) {
19 sign = v < 0 ? -1 : 1; v *= sign;
20 z.clear(); for (; v > 0; v = v / base) z.push_back((int) (v % base));
21 return *this;
22 }
23
24 bigint(const string &s) { read(s); }
25
26 bigint &operator+=(const bigint &other) {
27 if (sign == other.sign) {
28 for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
29 if (i == z.size())
30 z.push_back(0);
31 z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
32 carry = z[i] >= base;
33 if (carry)
34 z[i] -= base;
35 }
36 } else if (other != 0 /* prevent infinite loop */) {
37 *this -= -other;
38 }
39 return *this;
40 }
41
42 friend bigint operator+(bigint a, const bigint &b) { return a += b; }
43
44 bigint &operator-=(const bigint &other) {
45 if (sign == other.sign) {
46 if (sign == 1 && *this >= other || sign == -1 && *this <= other) {
47 for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
48 z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
49 carry = z[i] < 0;
50 if (carry)
51 z[i] += base;
52 }
53 trim();
54 } else {
55 *this = other - *this;
56 this->sign = -this->sign;
57 }
58 } else {
59 *this += -other;
60 }
61 return *this;
62 }
63
64 friend bigint operator-(bigint a, const bigint &b) { return a -= b; }
65
66 bigint &operator*=(int v) {
67 if (v < 0) sign = -sign, v = -v;
68 for (int i = 0, carry = 0; i < z.size() || carry; ++i) {
69 if (i == z.size())
70 z.push_back(0);
71 long long cur = (long long) z[i] * v + carry;
72 carry = (int) (cur / base);
73 z[i] = (int) (cur % base);
74 }
75 trim();
76 return *this;
77 }
78
79 bigint operator*(int v) const { return bigint(*this) *= v; }
80
81 friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
82 int norm = base / (b1.z.back() + 1);
83 bigint a = a1.abs() * norm;
84 bigint b = b1.abs() * norm;
85 bigint q, r;
86 q.z.resize(a.z.size());
87
88 for (int i = (int) a.z.size() - 1; i >= 0; i--) {
89 r *= base;
90 r += a.z[i];
91 int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
92 int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
93 int d = (int) (((long long) s1 * base + s2) / b.z.back());
94 r -= b * d;
95 while (r < 0)
96 r += b, --d;
97 q.z[i] = d;
98 }
99
100 q.sign = a1.sign * b1.sign;
101 r.sign = a1.sign;
102 q.trim();
103 r.trim();
104 return {q, r / norm};
105 }
106
107 friend bigint sqrt(const bigint &a1) {
108 bigint a = a1;
109 while (a.z.empty() || a.z.size() % 2 == 1)
110 a.z.push_back(0);
111
112 int n = a.z.size();
113
114 int firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
115 int norm = base / (firstDigit + 1);
116 a *= norm;
117 a *= norm;
118 while (a.z.empty() || a.z.size() % 2 == 1)
119 a.z.push_back(0);
120
121 bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];
122 firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
123 int q = firstDigit;
124 bigint res;
125
126 for (int j = n / 2 - 1; j >= 0; j--) {
127 for (;; --q) {
128 bigint r1 = (r - (res * 2 * base + q) * q) * base * base +
129 (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
130 if (r1 >= 0) {
131 r = r1;
132 break;
133 }
134 }
135 res *= base;
136 res += q;
137
138 if (j > 0) {
139 int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
140 int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
141 int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
142 q = (int) (((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2));
143 }
144 }
145
146 res.trim();
147 return res / norm;
148 }
149
150 bigint operator/(const bigint &v) const { return divmod(*this, v).first; }
151
152 bigint operator%(const bigint &v) const { return divmod(*this, v).second; }
153
154 bigint &operator/=(int v) {
155 if (v < 0) sign = -sign, v = -v;
156 for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
157 long long cur = z[i] + rem * (long long) base;
158 z[i] = (int) (cur / v);
159 rem = (int) (cur % v);
160 }
161 trim();
162 return *this;
163 }
164
165 bigint operator/(int v) const { return bigint(*this) /= v; }
166
167 int operator%(int v) const {
168 if (v < 0) v = -v;
169 int m = 0;
170 for (int i = (int) z.size() - 1; i >= 0; --i)
171 m = (int) ((z[i] + m * (long long) base) % v);
172 return m * sign;
173 }
174
175 bigint &operator*=(const bigint &v) { return *this = *this * v; }
176 bigint &operator/=(const bigint &v) { return *this = *this / v; }
177
178 bool operator<(const bigint &v) const {
179 if (sign != v.sign)
180 return sign < v.sign;
181 if (z.size() != v.z.size())
182 return z.size() * sign < v.z.size() * v.sign;
183 for (int i = (int) z.size() - 1; i >= 0; i--)
184 if (z[i] != v.z[i])
185 return z[i] * sign < v.z[i] * sign;
186 return false;
187 }
188
189 bool operator>(const bigint &v) const { return v < *this; }
190 bool operator<=(const bigint &v) const { return !(v < *this); }
191 bool operator>=(const bigint &v) const { return !(*this < v); }
192
193 bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); }
194
195 bool operator!=(const bigint &v) const { return *this < v || v < *this; }
196
197 void trim() {
198 while (!z.empty() && z.back() == 0) z.pop_back();
199 if (z.empty()) sign = 1;
200 }
201
202 bool isZero() const { return z.empty(); }
203
204 friend bigint operator-(bigint v) {
205 if (!v.z.empty()) v.sign = -v.sign;
206 return v;
207 }
208
209 bigint abs() const {
210 return sign == 1 ? *this : -*this;
211 }
212
213 long long longValue() const {
214 long long res = 0;
215 for (int i = (int) z.size() - 1; i >= 0; i--)
216 res = res * base + z[i];
217 return res * sign;
218 }
219
220 friend bigint gcd(const bigint &a, const bigint &b) {
221 return b.isZero() ? a : gcd(b, a % b);
222 }
223
224 friend bigint lcm(const bigint &a, const bigint &b) {
225 return a / gcd(a, b) * b;
226 }
227
228 void read(const string &s) {
229 sign = 1;
230 z.clear();
231 int pos = 0;
232 while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
233 if (s[pos] == '-')
234 sign = -sign;
235 ++pos;
236 }
237 for (int i = (int) s.size() - 1; i >= pos; i -= base_digits) {
238 int x = 0;
239 for (int j = max(pos, i - base_digits + 1); j <= i; j++)
240 x = x * 10 + s[j] - '0';
241 z.push_back(x);
242 }
243 trim();
244 }
245
246 friend istream &operator>>(istream &stream, bigint &v) {
247 string s; stream >> s;
248 v.read(s);
249 return stream;
250 }
251
252 friend ostream &operator<<(ostream &stream, const bigint &v) {
253 if (v.sign == -1)
254 stream << '-';
255 stream << (v.z.empty() ? 0 : v.z.back());
256 for (int i = (int) v.z.size() - 2; i >= 0; --i)
257 stream << setw(base_digits) << setfill('0') << v.z[i];
258 return stream;
259 }
260
261 static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
262 vector<long long> p(max(old_digits, new_digits) + 1);
263 p[0] = 1;
264 for (int i = 1; i < p.size(); i++)
265 p[i] = p[i - 1] * 10;
266 vector<int> res;
267 long long cur = 0;
268 int cur_digits = 0;
269 for (int v : a) {
270 cur += v * p[cur_digits];
271 cur_digits += old_digits;
272 while (cur_digits >= new_digits) {
273 res.push_back(int(cur % p[new_digits]));
274 cur /= p[new_digits];
275 cur_digits -= new_digits;
276 }
277 }
278 res.push_back((int) cur);
279 while (!res.empty() && res.back() == 0)
280 res.pop_back();
281 return res;
282 }
283
284 typedef vector<long long> vll;
285
286 static vll karatsubaMultiply(const vll &a, const vll &b) {
287 int n = a.size();
288 vll res(n + n);
289 if (n <= 32) {
290 for (int i = 0; i < n; i++)
291 for (int j = 0; j < n; j++)
292 res[i + j] += a[i] * b[j];
293 return res;
294 }
295
296 int k = n >> 1;
297 vll a1(a.begin(), a.begin() + k);
298 vll a2(a.begin() + k, a.end());
299 vll b1(b.begin(), b.begin() + k);
300 vll b2(b.begin() + k, b.end());
301
302 vll a1b1 = karatsubaMultiply(a1, b1);
303 vll a2b2 = karatsubaMultiply(a2, b2);
304
305 for (int i = 0; i < k; i++)
306 a2[i] += a1[i];
307 for (int i = 0; i < k; i++)
308 b2[i] += b1[i];
309
310 vll r = karatsubaMultiply(a2, b2);
311 for (int i = 0; i < a1b1.size(); i++)
312 r[i] -= a1b1[i];
313 for (int i = 0; i < a2b2.size(); i++)
314 r[i] -= a2b2[i];
315
316 for (int i = 0; i < r.size(); i++)
317 res[i + k] += r[i];
318 for (int i = 0; i < a1b1.size(); i++)
319 res[i] += a1b1[i];
320 for (int i = 0; i < a2b2.size(); i++)
321 res[i + n] += a2b2[i];
322 return res;
323 }
324
325 bigint operator*(const bigint &v) const {
326 vector<int> a6 = convert_base(this->z, base_digits, 6);
327 vector<int> b6 = convert_base(v.z, base_digits, 6);
328 vll a(a6.begin(), a6.end());
329 vll b(b6.begin(), b6.end());
330 while (a.size() < b.size())
331 a.push_back(0);
332 while (b.size() < a.size())
333 b.push_back(0);
334 while (a.size() & (a.size() - 1))
335 a.push_back(0), b.push_back(0);
336 vll c = karatsubaMultiply(a, b);
337 bigint res;
338 res.sign = sign * v.sign;
339 for (int i = 0, carry = 0; i < c.size(); i++) {
340 long long cur = c[i] + carry;
341 res.z.push_back((int) (cur % 1000000));
342 carry = (int) (cur / 1000000);
343 }
344 res.z = convert_base(res.z, 6, base_digits);
345 res.trim();
346 return res;
347 }
348
349};
350
351bigint random_bigint(int n) {
352 string s;
353 for (int i = 0; i < n; i++) {
354 s += rand() % 10 + '0';
355 }
356 return bigint(s);
357}
358
359// random tests
360void bigintTest() {
361 bigint x = bigint("120");
362 bigint y = bigint("5");
363 cout << x / y << endl;
364
365 for (int i = 0; i < 1000; i++) {
366 int n = rand() % 100 + 1;
367 bigint a = random_bigint(n);
368 bigint res = sqrt(a);
369 bigint xx = res * res;
370 bigint yy = (res + 1) * (res + 1);
371
372 if (xx > a || yy <= a) {
373 cout << i << endl;
374 cout << a << " " << res << endl;
375 break;
376 }
377
378 int m = rand() % n + 1;
379 bigint b = random_bigint(m) + 1;
380 res = a / b;
381 xx = res * b;
382 yy = b * (res + 1);
383
384 if (xx > a || yy <= a) {
385 cout << i << endl;
386 cout << a << " " << b << " " << res << endl;
387 break;
388 }
389 }
390
391 bigint a = random_bigint(10000);
392 bigint b = random_bigint(2000);
393 clock_t start = clock();
394 bigint c = a / b;
395 printf("time=%.3lfsec\n", (clock() - start) * 1. / CLOCKS_PER_SEC);
396}
397
398string str(bigint b) {
399 stringstream ss; ss << b;
400 string s; ss >> s;
401 return s;
402}
并查集
1namespace UF1{
2
3 class UnionFind{
4
5 private:
6 int* parent; // parent[i]表示第i个元素所指向的父节点
7 int* sz; // sz[i]表示以i为根的集合中元素个数
8 int count; // 数据个数
9
10 public:
11 // 构造函数
12 UnionFind(int count){
13 parent = new int[count];
14 sz = new int[count];
15 this->count = count;
16 for( int i = 0 ; i < count ; i ++ ){
17 parent[i] = i;
18 sz[i] = 1;
19 }
20 }
21
22 // 析构函数
23 ~UnionFind(){
24 delete[] parent;
25 delete[] sz;
26 }
27
28 // 查找过程, 查找元素p所对应的集合编号
29 // O(h)复杂度, h为树的高度
30 int find(int p){
31 assert( p >= 0 && p < count );
32 // 不断去查询自己的父亲节点, 直到到达根节点
33 // 根节点的特点: parent[p] == p
34 while( p != parent[p] )
35 p = parent[p];
36 return p;
37 }
38
39 // 查看元素p和元素q是否所属一个集合
40 // O(h)复杂度, h为树的高度
41 bool isConnected( int p , int q ){
42 return find(p) == find(q);
43 }
44
45 // 合并元素p和元素q所属的集合
46 // O(h)复杂度, h为树的高度
47 void unionElements(int p, int q){
48
49 int pRoot = find(p);
50 int qRoot = find(q);
51
52 if( pRoot == qRoot )
53 return;
54
55 // 根据两个元素所在树的元素个数不同判断合并方向
56 // 将元素个数少的集合合并到元素个数多的集合上
57 if( sz[pRoot] < sz[qRoot] ){
58 parent[pRoot] = qRoot;
59 sz[qRoot] += sz[pRoot];
60 }
61 else{
62 parent[qRoot] = pRoot;
63 sz[pRoot] += sz[qRoot];
64 }
65 }
66 };
67}
68
69
70namespace UF2{
71
72 class UnionFind{
73
74 private:
75 int* rank; // rank[i]表示以i为根的集合所表示的树的层数
76 int* parent; // parent[i]表示第i个元素所指向的父节点
77 int count; // 数据个数
78
79 public:
80 // 构造函数
81 UnionFind(int count){
82 parent = new int[count];
83 rank = new int[count];
84 this->count = count;
85 for( int i = 0 ; i < count ; i ++ ){
86 parent[i] = i;
87 rank[i] = 1;
88 }
89 }
90
91 // 析构函数
92 ~UnionFind(){
93 delete[] parent;
94 delete[] rank;
95 }
96
97 // 查找过程, 查找元素p所对应的集合编号
98 // O(h)复杂度, h为树的高度
99 int find(int p){
100 assert( p >= 0 && p < count );
101 // 不断去查询自己的父亲节点, 直到到达根节点
102 // 根节点的特点: parent[p] == p
103 while( p != parent[p] )
104 p = parent[p];
105 return p;
106 }
107
108 // 查看元素p和元素q是否所属一个集合
109 // O(h)复杂度, h为树的高度
110 bool isConnected( int p , int q ){
111 return find(p) == find(q);
112 }
113
114 // 合并元素p和元素q所属的集合
115 // O(h)复杂度, h为树的高度
116 void unionElements(int p, int q){
117
118 int pRoot = find(p);
119 int qRoot = find(q);
120
121 if( pRoot == qRoot )
122 return;
123
124 // 根据两个元素所在树的元素个数不同判断合并方向
125 // 将元素个数少的集合合并到元素个数多的集合上
126 if( rank[pRoot] < rank[qRoot] ){
127 parent[pRoot] = qRoot;
128 }
129 else if( rank[qRoot] < rank[pRoot]){
130 parent[qRoot] = pRoot;
131 }
132 else{ // rank[pRoot] == rank[qRoot]
133 parent[pRoot] = qRoot;
134 rank[qRoot] += 1; // 此时, 我维护rank的值
135 }
136 }
137 };
138}
直线划分平面
1while(cin>>n)
2 cout<<n*(n+1)/2+1<<endl;
判断两个线段相交
1# 点
2class Point(object):
3
4 def __init__(self, x, y):
5 self.x, self.y = x, y
6
7# 向量
8class Vector(object):
9
10 def __init__(self, start_point, end_point):
11 self.start, self.end = start_point, end_point
12 self.x = end_point.x - start_point.x
13 self.y = end_point.y - start_point.y
14
15
16ZERO = 1e-9
17
18def negative(vector):
19 """取反"""
20 return Vector(vector.end_point, vector.start_point)
21
22def vector_product(vectorA, vectorB):
23 '''计算 x_1 * y_2 - x_2 * y_1'''
24 return vectorA.x * vectorB.y - vectorB.x * vectorA.y
25
26def is_intersected(A, B, C, D):
27 '''A, B, C, D 为 Point 类型'''
28 AC = Vector(A, C)
29 AD = Vector(A, D)
30 BC = Vector(B, C)
31 BD = Vector(B, D)
32 CA = negative(AC)
33 CB = negative(BC)
34 DA = negative(AD)
35 DB = negative(BD)
36
37 return (vector_product(AC, AD) * vector_product(BC, BD) <= ZERO) \
38 and (vector_product(CA, CB) * vector_product(DA, DB) <= ZERO)
网络流
1struct Flow_Dinic {
2 Flow_Dinic(int n) {
3 head = vector<int>(n + 10, -1);
4 level = vector<int>(n + 10);
5 }
6
7 struct edge {
8 int to, cap, next;
9 };
10
11 vector<int> head;
12 vector<int> level;
13
14 int s = 0, t = 0; // max_flow from s to t
15
16 vector<struct edge> edge;
17
18 void add_edge(int u, int v, int c) {
19 edge.push_back((struct edge) {v, c, head[u]});
20 head[u] = edge.size() - 1;
21 edge.push_back((struct edge) {u, 0, head[v]});
22 head[v] = edge.size() - 1;
23 }
24
25 bool bfs() {
26 fill(level.begin(), level.end(), 0);
27 level[s] = 1;
28 queue<int> que;
29 que.push(s);
30 while (!que.empty()) {
31 for (int i = head[que.front()]; ~i; i = edge[i].next) {
32 if (edge[i].cap && !level[edge[i].to]) {
33 level[edge[i].to] = level[que.front()] + 1;
34 que.push(edge[i].to);
35 if (edge[i].to == t) return true;
36 }
37 }
38 que.pop();
39 }
40 return false;
41 }
42
43 int dfs(int f, int u) {
44 if (u == t) return f;
45 int d = 0, used = 0;
46 for (int i = head[u]; ~i; i = edge[i].next) {
47 if (edge[i].cap && level[u] == level[edge[i].to] - 1) {
48 if ((d = dfs(min(f - used, edge[i].cap), edge[i].to))) {
49 edge[i].cap -= d;
50 edge[i ^ 1].cap += d;
51 used += d;
52 }
53 }
54 }
55 if (!used) level[u] = 0;
56 return used;
57 }
58
59 long long run(int _s, int _t) {
60 s = _s;
61 t = _t;
62 long long max_flow = 0;
63 while (bfs()) {
64 int d = 0;
65 while ((d = dfs(0x3f3f3f3f, s))) max_flow += d;
66 }
67 return max_flow;
68 }
69 };
70
71
72struct Dinic {
73 Dinic(int n) {
74 G = vector<vector<int> >(n + 10);
75 d = vector<int> (n+10);
76 vis = vector<bool> (n+10);
77 cur = vector<int> (n+10);
78 }
79
80 struct Edge {
81 int from, to, cap, flow;
82 };
83
84 int s, t; //节点数,边数,源点编号,汇点编号
85 vector<Edge> edges; //边表,edges[e]和edges[e^1]互为反向弧
86 vector<vector<int> > G; //邻接表,G[i][j]表示节点i的第j条边在e中的序号
87 vector<bool> vis; //bfs用
88 vector<int> d; //从起点到i的距离
89 vector<int> cur; //当前弧下标
90 void add_edge(int from, int to, int cap) {
91 edges.push_back({from, to, cap, 0});
92 edges.push_back({to, from, 0, 0});
93 G[from].push_back(edges.size() - 2);
94 G[to].push_back(edges.size() - 1);
95 }
96
97 bool BFS() {
98 fill(vis.begin(), vis.end(), false);
99 queue<int> q;
100 q.push(s);
101 d[s] = 0;
102 vis[s] = true;
103 while (!q.empty()) {
104 for (int id : G[q.front()]) {
105 Edge &e = edges[id];
106 if (!vis[e.to] && e.cap > e.flow) {
107 vis[e.to] = true;
108 d[e.to] = d[q.front()] + 1;
109 q.push(e.to);
110 }
111 }
112 q.pop();
113 }
114 return vis[t];
115 }
116
117 long long DFS(int u, int a) {
118 if (u == t || a == 0) return a;
119 int flow = 0, f;
120 for (int &i = cur[u]; i < (int) G[u].size(); ++i) {
121 Edge &e = edges[G[u][i]];
122 if (d[u] + 1 == d[e.to] &&
123 (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
124 e.flow += f;
125 edges[G[u][i] ^ 1].flow -= f;
126 flow += f;
127 a -= f;
128 if (a == 0) break;
129 }
130 }
131 return flow;
132 }
133
134 long long run(int _s, int _t) {
135 s = _s;
136 t = _t;
137 long long flow = 0;
138 while (BFS()) {
139 fill(cur.begin(), cur.end(), 0);
140 flow += DFS(s, 0x3f3f3f3f);
141 }
142 return flow;
143 }
144};
最大子矩阵
1MOD(1e9+7);
2MAXN(1010);
3
4int mp[MAXN][MAXN], l[MAXN], r[MAXN];
5priority_queue <int> ans;
6
7void solve(){
8 FAST_IO;
9
10 int n, m;
11 cin >> n >> m;
12 loop(i, 1, n) loop(j, 1, m){
13 char c; cin >> c;
14 mp[i][j] = (c == '1');
15 }
16 loop(i, 2, n) loop(j, 1, m)
17 if(mp[i-1][j] && mp[i][j]) mp[i][j] += mp[i-1][j];
18 loop(i, 1, n){
19 set<pair<int, PII> > S;
20 stack<int> A, B;
21 loop(j, 1, m){
22 while(!A.empty() && mp[i][A.top()] >= mp[i][j]) A.pop();
23 l[j] = A.size() ? A.top()+1 : 1;
24 A.push(j);
25 }
26 for(int j = m; j >= 1; --j){
27 while(!B.empty() && mp[i][B.top()] >= mp[i][j]) B.pop();
28 r[j] = B.size() ? B.top() - 1 : m;
29 B.push(j);
30 }
31 loop(j, 1, m){
32 if(mp[i][j]){
33 pair<int, PII> temp = mp(r[j], mp(l[j], mp[i][j]));
34 pair<int ,PII> temp2;
35 if(!S.count(temp)){
36 ans.push((r[j] - l[j]+1)*mp[i][j]);
37 S.insert(temp);
38 }
39 if(r[j] - l[j]){
40 temp = mp(r[j], mp(l[j]+1, mp[i][j]));
41 temp2 = mp(r[j]-1, mp(l[j], mp[i][j]));
42 if(!S.count(temp)){
43 ans.push((r[j] - l[j]) * mp[i][j]);
44 S.insert(temp);
45 }else if(S.count(temp2)){
46 ans.push((r[j]-l[j])*mp[i][j]);
47 S.insert(temp2);
48 }
49 }
50 }
51 }
52 }
53 if(ans.size()<2) ans.push(0);
54 ans.pop();
55 cout << ans.top() << endl;
56
57}
58
59
60// 速度更快，但只能求前几大
61
62MOD(1e9+7);
63MAXN(1e3);
64
65int n, m;
66string s;
67int high[MAXN];
68
69int mxx, mxx2;
70int stkhg[MAXN], stkpos[MAXN];
71int cnt;
72
73void solve(){
74 FAST_IO;
75
76 cin >> n >> m;
77 high[m+1] = 0;
78 loop(i, 1, n){
79 cout << ">-- Line #" << i << " --<" << endl;
80 cin >> s;
81 loop(j, 1, m) high[j] = s[j-1]=='0' ? 0 : high[j]+1;
82#ifdef DEBUG
83 cout << "str: " << s << endl;
84 cout << "high: ";
85 loop(j, 1, m+1) cout << high[j] << ' ';
86 cout << endl;
87#endif
88 stkhg[0] = stkpos[0] = cnt = 0;
89 loop(j, 1, m+1){
90 if(high[j] > stkhg[cnt]){ // 如果比上一格高，说明可以构成矩形，就push进栈
91 stkhg[++cnt] = high[j];
92 stkpos[cnt] = j;
93 }else if(high[j] < stkhg[cnt]){ // 如果比上一格矮，
94 // 那么高度等于上一格高度的矩形已经完全找出来了，
95 // 当前格比上一格矮，不能参与构成上个矩形
96 while(high[j] < stkhg[cnt]){ // 将栈中高于当前位置的高度全部出栈
97 int area = (j-stkpos[cnt]) * stkhg[cnt]; // 当前位置坐标-比当前格高的格的坐标就是宽度
98 // 更新前两大矩形
99 if(area >= mxx){
100 mxx2 = mxx;
101 mxx = area;
102 mxx2 = max(mxx2, max(area-stkhg[cnt], area-(j-stkpos[j])));
103 }else if(area > mxx2){
104 mxx2 = area;
105 }
106 --cnt;
107 }
108 if(stkhg[cnt] != high[j]){
109 stkhg[++cnt] = high[j];
110 }
111 }
112#ifdef DEBUG
113 cout << j << " stkhg: ";
114 loop(j, 1, m+1) cout << stkhg[j] << ' ';
115 cout << endl;
116 cout << j << " stkpos: ";
117 loop(j, 1, m+1) cout << stkpos[j] << ' ';
118 cout << endl;
119 cout << "mxx: " << mxx << " mxx2: " << mxx2 << endl;
120#endif
121 }
122 }
123 cout << mxx2 << endl;
124
125}
拓展欧几里得
$_math_inline$ax+by=\gcd(a, b)$math_inline_$ 1void exgcd(LL a, LL b, LL &x, LL &y) {
2 if (b == 0) {
3 x = 1;y = 0;
4 } else {
5 exgcd(b, a%b, y, x);
6 y -= (a/b) * x;
7 }
8}
9
10void extgcd(LL a, LL b, LL &d, LL &x, LL &y) {
11 if (!b) {
12 d = a;
13 x = 1;
14 y = 0;
15 } else {
16 extgcd(b, a % b, d, y, x);
17 y -= x * (a / b);
18 }
19}
20
21LL inverse(LL a, LL n) {
22 LL d, x, y;
23 extgcd(a, n, d, x, y);
24 return d == 1 ? (x + n) % n : -1;
25}
递推求1~n的逆元
1const int N = 1e5 + 5;
2int inv[N];
3
4void inverse(int n, int p) {
5 inv[1] = 1;
6 for (int i = 2; i <= n; ++i) {
7 inv[i] = (ll) (p - p / i) * inv[p % i] % p;
8 }
9}
递推求n!的逆元
1// 快速幂求逆元
2int quick_inverse(int n, int p) {
3 int ret = 1;
4 int exponent = p - 2;
5 for (int i = exponent; i; i >>= 1, n = n * n % p) {
6 if (i & 1) {
7 ret = ret * n % p;
8 }
9 }
10 return ret;
11}
12int invf[N], factor[N];
13void get_factorial_inverse(int n, int p) {
14 factor[0] = 1;
15 for (int i = 1; i <= n; ++i) {
16 factor[i] = i * factor[i - 1] % p;
17 }
18 invf[n] = quick_inverse(factor[n], p);
19 for (int i = n-1; i >= 0; --i) {
20 invf[i] = invf[i + 1] * (i + 1) % p;
21 }
22}
lowbit
1lowbit(n) = n&(~n+1) = n&(-n)
数的那些位为1
1void f2(int n){
2 int H[37];
3 for(int i = 0; i < 36; ++i) H[(1ll << i) % 37] = i;
4 while(n > 0){
5 cout << H[(n & -n) % 37] << ' ';
6 n -= n & -n;
7 }
8 cout << endl;
9}
最短Hamilton路径
1int f[1 << 20][20], weight[20][20], n;
2
3int hamilton(int n, int weight[20][20]) {
4 memset(f, 0x3f, sizeof(f));
5 f[1][0] = 0;
6 for (int i = 1; i < 1 << n; i++)
7 for (int j = 0; j < n; j++) if (i >> j & 1)
8 for (int k = 0; k < n; k++) if ((i^1<<j) >> k & 1)
9 f[i][j] = min(f[i][j], f[i^1<<j][k]+weight[k][j]);
10 return f[(1 << n) - 1][n - 1];
11}
12
13int main() {
14 cin >> n;
15 for(int i = 0; i < n; i++)
16 for(int j = 0; j < n; j++)
17 scanf("%d", &weight[i][j]);
18 cout << hamilton(n, weight) << endl;
19}
卡特兰数
前三十项卡特兰数表
1[1,1,2,5,14,42,132,429,1430,4862,16796,58786,
2 208012,742900,2674440,9694845,35357670,129644790,
3 477638700,1767263190,6564120420,24466267020,
4 91482563640,343059613650,1289904147324,
5 4861946401452,18367353072152,69533550916004,
6 263747951750360,1002242216651368,3814986502092304]
卡特兰数求模模板
1const int C_maxn = 1e4 + 10;
2LL CatalanNum[C_maxn];
3LL inv[C_maxn];
4inline void Catalan_Mod(int N, LL mod)
5{
6 inv[1] = 1;
7 for(int i=2; i<=N+1; i++)///线性预处理 1 ~ N 关于 mod 的逆元
8 inv[i] = (mod - mod / i) * inv[mod % i] % mod;
9
10 CatalanNum[0] = CatalanNum[1] = 1;
11
12 for(int i=2; i<=N; i++)
13 CatalanNum[i] = CatalanNum[i-1] * (4 * i - 2) %mod * inv[i+1] %mod;
14}
卡特兰大数模板
1#include<bits/stdc++.h>
2using namespace std;
3const int C_maxn = 100 + 10;///项数
4
5int Catalan_Num[C_maxn][1000];///保存卡特兰大数、第二维为具体每个数位的值
6int NumLen[C_maxn];///每个大数的数长度、输出的时候需倒序输出
7
8void catalan() //求卡特兰数
9{
10 int i, j, len, carry, temp;
11 Catalan_Num[1][0] = NumLen[1] = 1;
12 len = 1;
13 for(i = 2; i < 100; i++)
14 {
15 for(j = 0; j < len; j++) //乘法
16 Catalan_Num[i][j] = Catalan_Num[i-1][j]*(4*(i-1)+2);
17 carry = 0;
18 for(j = 0; j < len; j++) //处理相乘结果
19 {
20 temp = Catalan_Num[i][j] + carry;
21 Catalan_Num[i][j] = temp % 10;
22 carry = temp / 10;
23 }
24 while(carry) //进位处理
25 {
26 Catalan_Num[i][len++] = carry % 10;
27 carry /= 10;
28 }
29 carry = 0;
30 for(j = len-1; j >= 0; j--) //除法
31 {
32 temp = carry*10 + Catalan_Num[i][j];
33 Catalan_Num[i][j] = temp/(i+1);
34 carry = temp%(i+1);
35 }
36 while(!Catalan_Num[i][len-1]) //高位零处理
37 len --;
38 NumLen[i] = len;
39 }
40}
41
42int main(void)
43{
44 catalan();
45 for(int i=1; i<=30; i++){
46 for(int j=NumLen[i]-1; j>=0; j--){
47 printf("%d", Catalan_Num[i][j]);
48 }puts("");
49 }
50 return 0;
51}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。