魔のkyo的BLOG
0%

发表于 更新于 分类于 Valine： 本文字数： 784 阅读时长 ≈ 1 分钟

上次在讲幂模算法时提到，对于a^b%m，指数b不能令b=b%m使b变小，但是让b=b%phi(m)，其中phi是欧拉函数。

欧拉函数phi(m)的值是模m的缩系的元素个数，小于m的与m互质的自然数构成模m的缩系。

所以phi(m)也是小于等于m并与m互质的自然数的个数。

但是用gcd（最大公约数）来统计与m互质的自然数是比较慢的。

欧拉函数有一个快速算法

1
2
3
4
5
6
7
ll phi(ll n) {
    auto factors = factorize(n);
    for(auto [p, k] : factors) {
        n = n / p * (p-1);
    }
    return n;
}

其中factorize(n)是将n因数分解，返回值是一个vector<pair<ll/*因子p*/, int/*指数k*/>>

n=Πpikin = \Pi p_i ^ {k_i}

相当于对n的每个质因子做了一个操作，除以n的所有的质因子一次，乘以所有(质因子-1)一次，得到的结果就是n的欧拉函数值。

factorize可以用如下实现

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> result;
    while(n!=1) {
        ll p = min_divisor(n);
        int c = 0;
        do {
            n/=p;
            ++c;
        } while(n%p==0);
        result.emplace_back(make_pair(p, c));
    }
    return result;
}

其中min_divisor(n)是n的最小因数（显然也一定是质因数）

min_divisor可以通过预处理的方式打质数表，有线性时间复杂度的质数筛法

发表于 分类于 Valine： 本文字数： 227 阅读时长 ≈ 1 分钟

正确的做法是

1
DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )"

搜索时经常看到有人说

1
DIR=$(cd $(dirname $0);pwd)

这种写法是有问题的，它不能被用于通过source调用的脚本

比如我们需要通过一个.sh设置环境变量，这个环境变量的值需要用到.sh所在路径，那我们就需要通过source去调用脚本。

发表于 分类于 Valine： 本文字数： 879 阅读时长 ≈ 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
string Manacher(string s)
{
    if (s.size() < 2) return s;
    // 第一步：预处理，将原字符串转换为新字符串
    stringstream ss;
    ss << '^';
    for (int i=0; i<s.size(); i++) {
        ss << '#' << s[i];
    }
    // 尾部再加上字符$，变为奇数长度字符串
    ss << '#' << '$';
    string t = ss.str();
    // 第二步：计算数组p、起始索引、最长回文半径
    int n = t.size();
    // p数组
    vector<int> p(n);
    int id = 0, mx = 0;
    // 最长回文子串的长度
    int maxLength = -1;
    // 最长回文子串的中心位置索引
    int index = 0;
    for (int j=1; j<n-1; j++) {
        // 计算p数组
        p[j] = mx > j ? min(p[2*id-j], mx-j) : 1;
        // 向左右两边延伸，扩展右边界
        while (t[j+p[j]] == t[j-p[j]]) {
            p[j]++;
        }
        // 如果回文子串的右边界超过了mx，则需要更新mx和id的值
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
        // 如果回文子串的长度大于maxLength，则更新maxLength和index的值
        if (maxLength < p[j] - 1) {
            maxLength = p[j] - 1;
            index = j;
        }
    }
    // 第三步：截取字符串，输出结果
    int start = (index-maxLength)/2;
    return s.substr(start, maxLength);
}

发表于 更新于 分类于 Valine： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

非负数序列的第 k 小子序列和

先把所有数从小到大排序。设一个二元组 (sum, i) 表示以第 i 位为结尾，和为 sum 的子序列，用一个小根堆来维护这些二元组，以(arr[0], 0)为初始二元组，每次取出堆顶，然后把 (sum+arr[i+1], i+1) 和 (sum+arr[i+1]−arr[i], i+1) 加入堆中，以此来生成所有的子序列和，而且生成步骤每次都是取出当前最小的。

所以第 k 个被取出的堆顶就是答案。

PS: 虽然上述步骤可以逐个生成所有的第k小子序列和，但若len(arr) = n，因为arr中每个数都可以出现在序列或不出现在序列，因为共有2n种组合，因为k的范围是很大的，而算法的复杂度是O(nlogn)+O(klogk)，所以k的实际上是受限的，一般不能超过105

第 k 小子序列和（允许有负数）

当序列中有负数时，我们还是用前面的思路从最小和序列逐个生成，而这时最小和序列是包含所有负数的子序列，生成的过程是不断去掉一个负数或者加上一个正数情况会变得复杂，我们可以先算出所有负数的和作为最小和min_sum，其他的和都是在这个基础上减去一些正数或加上一些负数生成的，当arr[i]是负数时因为已经在最小基础和min_sum里了，在生成新和时总是减掉这个负数相当于加上负数的绝对值，而当arr[i]是正数时因为不在min_sum里，在生成新和时总是加上正数，因此我们可以把正负数统一按绝对值处理，用min_sum加上序列abs(arr)的某个子序列和，就是原序列的相应的子序列和，序列abs(arr)是arr的绝对值形成的序列，它的子序列和则可以规约到前面已经讨论过的非负数序列的第 k 小子序列和问题了。

第 k 大子序列和（允许有负数）

因为第k小子序列和的k受限，本问题不能简单规约到第2^n-1-k小子序列和解决，

我们可以先算出所有正数的和作为最大和max_sum，其他的和都是在这个基础上减去一些正数或加上一些负数生成的。

我们还是可以把正负数统一处理，我们可以把问题规约为 max_sum - kMinSum(abs(arr), k)，其中abs(arr)表示对arr中每个元素取绝对值形成的数组。

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

typedef long long ll;

struct Node {
    ll sum;
    int i;
};

// 求非负整数数组nums的第k小子序列和，k=0,1,2,...,2^n-1
// 算法复杂度是O(nlogn)+O(klogk), n=nums.size()
// 所以n和k的规模都是受限的，一般不能超过10^5
ll kMinSumBase(const vector<int>& nums, int k) {
    vector<int> arr = nums;
    sort(arr.begin(), arr.end());
    auto cmp = [&](const Node& a, const Node& b) {
        return a.sum > b.sum;
    };
    priority_queue<Node, vector<Node>, decltype(cmp)> PQ(cmp);
    PQ.push(Node{arr[0], 0});
    PQ.push(Node{0, -1}); // 特殊处理空子段
    ll result = 0;
    for(int i=0;i<k && !PQ.empty();i++) {
        auto node = PQ.top(); PQ.pop();
        if(node.i != -1 && node.i+1 < arr.size()) {
            PQ.push(Node{node.sum+arr[node.i+1], node.i+1});
            PQ.push(Node{node.sum+arr[node.i+1]-arr[node.i], node.i+1});
        }
    }
    assert(!PQ.empty());
    auto node = PQ.top(); PQ.pop();
    return node.sum;
}

// 求数组nums（允许有负数）的第k小子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMinSum(const vector<int>& nums, int k) {
    ll min_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] < 0) {
            min_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return min_sum + kMinSumBase(arr, k);
}

// 求数组nums（允许有负数）的第k大子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMaxSum(const vector<int>& nums, int k) {
    ll max_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] > 0) {
            max_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return max_sum - kMinSumBase(arr, k);
}

发表于 更新于 分类于 Valine： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

幂模就是求 a^b%m 的问题，a、b、m都是整数，a和b可能很大，a^b会超过整数表示范围，而m在整数范围内的数。

首先我们知道 x * y % m = (x % m) * (y % m) % m（证明略，设x=p_1 m+q_1, y =p_2 m+q_2很容易证明）

这意味着我们可以在计算 a ^ b 的过程中对中间值进行模m操作从而缩小中间值，而这不会影响最终结果。

然后我们可以把指数b分解成二进制，以次算出a^1, a^2, a^4, a^8,… 当b的二进制从最低位算第k位是1的时候，我们就的结果就应该乘入a^(1<<k)。

1
2
3
4
5
6
7
8
9
10
11
12
//思想a^13=a^(1+4+8)=a^1*a^4*a^8
int modExp(int a,int b,int m) {
	int t=1,y=a%m;
	while(b){
		if(b&1){
			t=t*y%m;
		}
		y=y*y%m;
		b=(b>>1);
	}
	return t;
}

这就是快速幂模算法。

我们进一步，如果a更大，本身就超出了int范围，我们用string类型存储，如何快速求出a^b%m呢？

其实很简单，我们可以用一个循环把a转换成整数

1
2
3
4
int r = 0;
for(int i=0;i<a.size();i++) {
	r  = r * 10 + (a[i]-'0');
}

这个结果当然会导致r超过int表示范围，但是我们在过程的中间值就进行模m操作就可以了

1
2
3
4
5
6
7
8
9
10
11
12
int str2int(const string& a, int m) {
    int r = 0;
    for(int i=0;i<a.size();i++) {
        r  = (r * 10 + (a[i]-'0')) % m;
    }
    return r;
}

int modExp(const string& a, int b, int m) {
    return modExp(str2int(a, m), b, m);
}

在进一步，如果b也更大，本身就超出了int范围，我们用string类型存储，如何快速求出 a^b%m呢？

很自然我们会想能否把b像a一样也在转成int的同时处理成b%m呢？答案是否定的。我们可以用反证法证明：

设上述问题可以先把b处理成b%m，即 a^b%m 和 a^(b%m)%m 相等，易推得 a^m%m=1，因为这里a，b，m都是任取的，所以我们只要找到一个反例不满足 a^m%m=1就可以推得矛盾，我们可以找2^3%3 = 2 != 3，证毕。

实际上我们可以先把b处理成 b%\phi(m) ，其中phi是欧拉函数，phi(m)等于1~m中和m互质的数的个数，我会另开文章讨论欧拉函数，在此先另辟蹊径解决此问题。

\begin{align} &~~~~~a ^ b\\ &= a^{b_0*10^{n-1}+b_1*10^{n-2}+...+b_{n-1}*10^0}, 其中n=len(b), b_i是b的左起第i位数字\\ &= a^{b_0*10^{n-1}}*a^{b_1*10^{n-2}}*...*a^{b_{n-1}*10^0}\\ &= (a^{10^{n-1}})^{b_0}*(a^{10^{n-2}})^{b_1}*...*(a^{10^0})^{b_{n-1}} \end{align}

其中

a10k=(a10k−1)10a^{10^k} = (a ^ {10^{k-1}})^{10}

这样我们就可以倒序遍历b的每位，并在过程中用上式维护a(10k)

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
int modExp(int a,int b,int m) {
    int t=1,y=a%m;
    while(b){
        if(b&1){
            t=t*y%m;
        }
        y=y*y%m;
        b=(b>>1);
    }
    return t;
}

int str2int(const string& a, int m) {
    int r = 0;
    for(int i=0;i<a.size();i++) {
        r  = (r * 10 + (a[i]-'0')) % m;
    }
    return r;
}

int modExp(const string& a, const string& b, int m) {
    int r = 1;
    int a10k = str2int(a, m);
    for(int i=b.size()-1;i>=0;i--) {
        r = r * modExp(a10k, b[i]-'0', m) % m;
        a10k = modExp(a10k, 10, m);
    }
    return r;
}

还要注意的一点是，m虽然限定在int范围内，但是如果m*m超出了int，则计算过程中的乘法可能会超出int，为了防止溢出我们可以把数据类型换成long long，并且可以用模加来实现模乘来降低溢出的可能。

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
ll modMul(ll a,ll b,ll m) {
    ll t=0;
    a=(a%m+m)%m;
    b=(b%m+m)%m;
    while(b){
        if(b&1){
            t=(t+a)%m;
        }
        a=(a+a)%m;
        b>>=1;
    }
    return t;
}

ll modExp(ll a,ll b,ll m) {
    ll t=1,y=a%m;
    while(b){
        if(b&1){
            t=modMul(t,y,m);
        }
        y=modMul(y,y,m);
        b=(b>>1);
    }
    return t;
}

发表于 分类于 Valine： 本文字数： 1.2k 阅读时长 ≈ 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

template<typename R, typename T>
R sstream_cast(const T& o) {
    stringstream ss;
    ss << o;
    R result;
    ss >> result;
    return result;
}

// 排列数 n!/(n-k)!
int P(int n,int k)
{
        if(k>n)return 0;
        int res = 1;
        for(int i=n-k+1; i<=n; i++){
            res *= i;
        }
        return res;
}

// 返回小于n的各个数位不同的整数的个数
int countDistinctDigitsNumbers(int n) {
    string s = sstream_cast<string>(n);
    int len = s.size();
    // 分类考虑：
    // 1. 所有位数不足len的数满足条件
    // 2. 首位为 1 ~ s[0]-1 的情况，s[1:len]任意都满足条件
    // 3. 首位为 s[0]，二位为 0 ~ s[1]-1 的情况(但前缀用掉的digit不能再用)，s[2:len]任意都满足条件
    //    ...
    //    前缀为 s[0:i]，第i位为 0 ~ s[i]-1 的情况(但前缀用掉的digit不能再用)，s[i+1:len]任意都满足条件
    //    ...
    //    前缀为 s[0:len-1]，第len-1位为 0 ~s[len-1]-1 的情况(但前缀用掉的digit不能再用)，空后缀

    int result = 0;
    // 第1类：统计任意i位数的个数
    for(int i=1;i<len;i++) {
        result += 9 * P(9, i-1);
    }
    // 第2类
    result += (s[0]-'0'-1) * P(9, len-1);
    // 第3类
    bool used[10] = {0};
    used[s[0]-'0'] = true;
    for(int i=1;i<len;i++) {
        int cnt = 0;
        // 对于cnt的循环计数可以优化，但无必要
        for(int k=0;k<s[i]-'0';k++) {
            if(!used[k]) {
                cnt++;
            }
        }
        result += cnt * P(9-i, len-1-i);

        // 如果s前缀本身用到了重复数字，直接跳出，终止第3类的计算
        if(used[s[i]-'0']) break;
        else used[s[i]-'0'] = true;
    }
    return result;
}

发表于 更新于 分类于 Valine： 本文字数： 2.1k 阅读时长 ≈ 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
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
# -*- coding: utf-8 -*-
import traceback
import smtplib
import os
from email.mime.text import MIMEText
from email.mime.multipart import MIMEMultipart
from email.mime.application import MIMEApplication
from email.utils import formataddr as _formataddr

def formataddr(addr):
    return ','.join([_formataddr([a.split("@")[0].strip(), a.strip()]) for a in addr.split(',')])

"""
smtp_server: SMTP服务器地址
from_addr: 发件人地址
to_addr: 收件人地址（多个地址用英文逗号分割）
subject: 邮件主题
content: 邮件内容
attachmentpaths: 附件的文件路径
html: 邮件内容是否是HTML格式
ssl: 使用SMTP_SLL（465端口）还是SMTL（25端口）
"""
def send_email(smtp_server, from_addr, password, to_addr, subject, content, attachmentpaths=[], html=False, ssl=True):
    try:
        msg = MIMEMultipart()
        msg['From'] = formataddr(from_addr)  # 括号里的对应发件人邮箱昵称、发件人邮箱账号
        msg['To'] = formataddr(to_addr)      # 括号里的对应收件人邮箱昵称、收件人邮箱账号
        msg['Subject'] = subject             # 邮件标题
        if html:
            context_part = MIMEText(content, 'html', 'utf-8')
        else:
            context_part = MIMEText(content, 'plain', 'utf-8')
        msg.attach(context_part)

        if attachmentpaths:
            for path in attachmentpaths:
                filedir, filename = os.path.split(path)
                part = MIMEApplication(open(path,'rb').read()) 
                part.add_header('Content-Disposition', 'attachment', filename=filename) 
                msg.attach(part)

        if ssl:
            server=smtplib.SMTP_SSL(smtp_server, 465)
        else:
            server=smtplib.SMTP(smtp_server, 25)  # 发件人邮箱中的SMTP服务器，端口是25
        server.login(from_addr, password)  # 括号中对应的是发件人邮箱账号、邮箱密码
        server.sendmail(from_addr, to_addr.split(','), msg.as_string())
        server.quit()  # 关闭连接
        return True
    except Exception:
        traceback.print_exc()
        return False

if __name__ == '__main__':
    # test

    send_email("smtp.163.com", "kyo_86@163.com", "XXXXXXXXX", "kyo_86@163.com",
                f"测试HTML内容和附件发送",
                """
<html>
<body>
    <img src="http://kyo86.com/images/saber.jpg"/>
</body>
</html>
                """,
                attachmentpaths=[r"./mailer.py"], html=True, ssl=True)

发表于 更新于 分类于 Valine： 本文字数： 5.4k 阅读时长 ≈ 5 分钟 
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
# -*- coding: utf-8 -*-
import imaplib
imaplib._MAXLINE = 10000000
import email
import email.utils
import re
import os
import datetime
import pytz
import traceback
from dataclasses import dataclass


def decode(s, charset):
    if type(s) is str:
        return s
    try:
        return s.decode(charset)
    except Exception:
        pass
    try:
        return s.decode('utf-8')
    except Exception:
        pass
    try:
        return s.decode('latin1')
    except Exception as e:
        pass
    return s.decode('gbk')


class Attachment:
    def __init__(self, part):
        self.content_type = part.get_content_type()
        raw_filename = part.get_filename() # .strip()
        # print(dir(part), raw_filename)
        if raw_filename.startswith("=?") and raw_filename.endswith("?="):
            dh = email.header.decode_header(raw_filename)
            self.filename = decode(dh[0][0], dh[0][1])
        else:
            h = email.header.Header(raw_filename)
            dh = email.header.decode_header(h)
            self.filename = decode(dh[0][0], dh[0][1])
        self.data = part.get_payload(decode=True) #下载附件

    def __repr__(self):
        return f"Attachment(content_type='{self.content_type}', filename='{self.filename}', size={len(self.data)})"

    def save_to(self, path):
        if os.path.exists(path):
            if os.path.isdir(path): # 已附件原文件名保存到目录下
                path = os.path.join(path, self.filename)
                with open(path, 'wb') as fp:
                    fp.write(self.data)
            else: # 覆盖已存在文件
                with open(path, 'wb') as fp:
                    fp.write(self.data)
        else: # 新建文件
            with open(path, 'wb') as fp:
                fp.write(self.data)


class Mail:
    def __init__(self, num, msg):
        # 这些字段是在读取邮件列表时就解析的
        self.num = num
        self.subject: str = self._decode_value(msg.get("subject"))
        date = email.utils.parsedate_to_datetime(msg.get("date"))
        if date:
            timezone = pytz.timezone('Asia/Shanghai')
            date = date.astimezone(timezone) # 设置时区为+8区
            date = date.replace(tzinfo=None) # 移除时区信息
        self.date: str = str(date) if date else msg.get("date")
        from_name, self.from_addr = email.utils.parseaddr(msg.get("from"))
        self.from_name = self._decode_value(from_name)
        to_name, self.to_addr = email.utils.parseaddr(msg.get("to"))
        self.to_name = self._decode_value(to_name)

        # 这些字段是延迟到需要访问时才解析的
        self._plain: str = ""
        self._html: str = ""
        self._attachments: list = []

        self._msg: str = msg
        self._parsed: bool = False

    def _decode_value(self, value):
        try:
            header = email.header.decode_header(value)
            raw_value = email.header.decode_header(value)[0][0]
            charset = email.header.decode_header(value)[0][1]
            return decode(raw_value, charset)
        except Exception as e:
            print(f"decode failed [value] {value}")
            traceback.print_exc()
            return None

    @property
    def plain(self):
        # 为了延迟解析邮件内容
        if not self._parsed:
            self.parse_content()
        return self._plain

    @property
    def html(self):
        if not self._parsed:
            self.parse_content()
        return self._html

    @property
    def attachments(self):
        if not self._parsed:
            self.parse_content()
        return self._attachments

    # 解析mail的内容
    def parse_content(self):
        self._attachments = []
        for part in self._msg.walk():
            if part.is_multipart():
                continue
            if part.get_content_type() == "text/plain":
                charset = part.get_content_charset()
                content = decode(part.get_payload(decode=True), charset)
                self._plain = content
            if part.get_content_type() == "text/html":
                charset = part.get_content_charset()
                content = decode(part.get_payload(decode=True), charset)
                self._html = content
            
            if part.get_content_disposition():
                if part.get_content_disposition() == "inline":
                    # HTML内容引用的图片之类的
                    pass
                elif part.get_content_disposition() == "attachment":
                    # 附件
                    self._attachments.append(Attachment(part))
        if self._plain:
            self._html = ""
        self._parsed = True

        
class ImapMailBox:
    def __init__(self, host, port, username, password):
        self.host = host
        self.port = port
        self.username = username
        self.password = password
        # connecting to host via SSL
        self.conn = imaplib.IMAP4_SSL(host=host, port=port)
        # logging in to servers
        self.conn.login(username, password)

    def get_mail_count(self):
        # Selecting the inbox of the logged in account
        self.conn.select('Inbox')
        state, data = self.conn.search(None, 'ALL')
        mail_list = []
        mails = data[0].split()
        return len(mails)

    def get_mail_list(self, page=1, page_size=50):
        # Selecting the inbox of the logged in account
        self.conn.select('Inbox')
        state, data = self.conn.search(None, 'ALL')
        mail_list = []
        mails = data[0].split()[::-1]
        if page_size:
            mails = mails[(page-1)*page_size: page*page_size]
        for num in mails:
            state, data = self.conn.fetch(num, '(RFC822)')
            raw_email = data[0][1]
            try:
                msg = email.message_from_bytes(raw_email)
                mail = Mail(num, msg)
                mail_list.append(mail)
            except Exception as e:
                print(f"Parse raw data failed. [raw_data] '{raw_email}'")
                traceback.print_exc()
        return mail_list

    def mark_as_seen(self, mail):
        self.conn.store(mail.num, '+FLAGS', '\\seen')

        
if __name__ == '__main__':
    mailbox = ImapMailBox(
        host='imap.aliyun.com', port=993,
        username="******", password="******"
        )
    count = mailbox.get_mail_count()
    # 收件箱里的邮件数
    print(count)
    # 分页获取邮件
    for mail in mailbox.get_mail_list(page=1, page_size=25):
        # 打印 日期、发件人、标题、纯文本内容
        print(mail.date, mail.from_addr, mail.subject, mail.plain)
		
        # 如果有附件，就下载保存到本地
        if mail.attachments:
            for attachment in mail.attachments:
                attachment.save_to("./")

发表于 更新于 分类于 Valine： 本文字数： 12k 阅读时长 ≈ 11 分钟

在LeetCode上提交的C代码并不需要include标准库头文件，判题系统会自动包含，并且在二叉树的题目会额外包含TreeNode结构。我希望有一个简洁的main.cpp可以直接提交到LeetCode，里面包含一些最常用的函数，调试输出的代码放在bits/stdc.h中（故意和标准库头文件同名），通过宏定义只在引入本地自定义的bits/stdc++.h时开启cout输出，这样可以直接把main.cpp的全部内容直接提交到网站条件，会自动屏蔽掉所有调试输出代码而不会报错。

main.cpp

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
#include "bits/stdc++.h"
using namespace std;

#define all(a) (a).begin(), (a).end()
template<typename T, typename F=less<T>>
using pque=priority_queue<T, vector<T>, F>;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef vector<vs> vvs;

template <typename T>
T max(const T& a, const T& b, const T& c) { return max(max(a, b), c); }
template <typename T>
T max(const vector<T>& a) {T r = a[0]; for(auto e : a) r = max(r, e); return r;}
template <typename T>
T min(const T& a, const T& b, const T& c) { return min(min(a, b), c); }
template <typename T>
T min(const vector<T>& a) {T r = a[0]; for(auto e : a) r = min(r, e); return r;}
template<typename T>
T sum(const vector<T>& a) { T r = 0; for(auto& e : a) r+=e; return r;}
template<typename T>
T gcd(T a, T b) { while(b) { T r = a%b; a = b; b = r;} return a;}
template<typename T>
T lcm(T a, T b) { return a/gcd(a,b)*b; }
template<typename F>
ll lb(ll b, ll e, F f) {if(b>=e) return e; while(b<e-1) {auto m=b+(e-1-b)/2; if(!f(m)) b=m+1; else e=m+1;} return f(b)?b:e;}
template<typename T>
struct cast_helper {T operator() (stringstream& ss) {T r=T{}; ss >> r; return r;}};
template<>
struct cast_helper<string> {string operator() (stringstream& ss) { return ss.str();}};
template<typename R, typename T>
R sstream_cast(const T& o) {stringstream ss; ss << o; return cast_helper<R>()(ss);}
string fmt(const char* f, ...){va_list a; va_start(a, f); char b[4096]; vsnprintf(b, 4096, f, a); va_end(a); return b;}

vvi make_vvi(int n, int m, int v=0) { return vvi(n, vi(m, v));}
vvb make_vvb(int n, int m, bool v=false) { return vvb(n, vb(m, v));}
vvs make_vvs(int n, int m, const string& v="") { return vvs(n, vs(m, v));}
typedef tuple<ll, ll> tii;
typedef tuple<int, int, int> tiii;
namespace std {
template<>struct hash<tii>{size_t operator()(const tii& a)const {return get<0>(a)^get<1>(a);}};
template<>struct hash<tiii>{size_t operator()(const tiii& a)const {return get<0>(a)^get<1>(a)^get<2>(a);}};
};
tii dir4[] = {tii(-1, 0), tii(0, 1), tii(1, 0), tii(0,-1)};
tii dir8[] = {tii(-1, 0), tii(0, 1), tii(1, 0), tii(0,-1), tii(-1,-1), tii(-1,1), tii(1,1), tii(1,-1)};
tii& operator += (tii& a, const tii& b) { get<0>(a)+=get<0>(b); get<1>(a)+=get<1>(b); return a; }
tii operator + (const tii& a, const tii& b) { return tii(get<0>(a)+get<0>(b), get<1>(a)+get<1>(b)); }
tii& operator -= (tii& a, const tii& b) { get<0>(a)-=get<0>(b); get<1>(a)-=get<1>(b); return a; }
tii operator - (const tii& a, const tii& b) { return tii(get<0>(a)-get<0>(b), get<1>(a)-get<1>(b)); }
tii operator - (const tii& a) { return tii(-get<0>(a), -get<1>(a)); }
tii& operator *= (tii& a, int k) { get<0>(a)*=k; get<1>(a)*=k; return a; }
tii operator * (int k, const tii& a) { return tii(k*get<0>(a), k*get<1>(a)); }
tii operator * (const tii& a, int k) { return tii(get<0>(a)*k, get<1>(a)*k); }
tii& operator /= (tii& a, int k) { get<0>(a)/=k; get<1>(a)/=k; return a; }
tii operator / (const tii& a, int k) { return tii(get<0>(a)/k, get<1>(a)/k); }
bool in_range(tii p, tii e) {return 0<=get<0>(p)&&get<0>(p)<get<0>(e)&&0<=get<1>(p)&&get<1>(p)<get<1>(e);}
bool in_range(tii p, tii b, tii e) {return get<0>(b)<=get<0>(p)&&get<0>(p)<get<0>(e)&&get<1>(b)<=get<1>(p)&&get<1>(p)<get<1>(e);}

#ifndef cout
struct _ {
    template <typename T>
    _& operator << (const T&){ return *this; }
};
#define cout _()
#define endl '\n'
#endif


int _main_()
{
    
    return 0;
}

#undef cout
#undef endl

一定要在结尾undef掉，不然会导致LeetCode误判

bits/stdc++.h

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
// #include <bits/stdc++.h>
#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <tuple>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <thread>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdarg>
using namespace std;

template<typename T>
T _s(const T& t) {return t;}
string _s(const string& t) {return '"'+ t + '"';}

template<typename T1, typename T2>
ostream& operator << (ostream& out, const pair<T1, T2>& o) {
    return out << "(" << o.first << ", " << o.second << ")";
}

template<typename T>
ostream& operator << (ostream& out, const vector<T>& v) {
    out << "[";
    for(int i=0;i<v.size();i++) {
        out << _s(v[i]) << (i != v.size() -1 ? ", " : "");
    }
    return out << "]";
}

template<typename T>
ostream& operator << (ostream& out, const vector<vector<T>>& v) {
    out << "[";
    for(int i=0;i<v.size();i++) {
        out << (i!=0?" ":"") << "[";
        for(int j=0;j<v[i].size();j++) {
            out << setw(5) << _s(v[i][j]) << (j != v[i].size() -1 ? ", " : "");
        }
        out << "]" << (i != v.size() -1 ? ",\n" : "");
    }
    return out << "]";
}

template<typename TK, typename TV>
ostream& operator << (ostream& out, const map<TK,TV>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template<typename TK, typename TV>
ostream& operator << (ostream& out, const multimap<TK,TV>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template<typename TK, typename TV>
ostream& operator << (ostream& out, const unordered_map<TK,TV>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template<typename T>
ostream& operator << (ostream& out, const set<T>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template<typename T>
ostream& operator << (ostream& out, const multiset<T>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template<typename T>
ostream& operator << (ostream& out, const unordered_set<T>& m) {
    out << "{";
    auto itr=m.begin();
    if(itr != m.end()) {
        out << *itr;
        for(itr++;itr!=m.end();itr++) {
            out << ", " << *itr;
        }
    }
    return out << "}";
}

template <size_t N>
struct PrintHelper;

template <>
struct PrintHelper<1>
{
    template<typename... Args>
    static void recursive_print(ostream& out, const tuple<Args...> t)
    {
        out << "(" << std::get<0>(t) << ", ";
    }
};

template <size_t N>
struct PrintHelper
{
    template<typename... Args>
    static void recursive_print(ostream& out, const tuple<Args...> t)
    {
        PrintHelper<N - 1>::recursive_print(out, t);
        out << std::get<N - 1>(t) << ", ";
    }

    template<typename... Args>
    static void print(ostream& out, const tuple<Args...> t)
    {
        PrintHelper<N - 1>::recursive_print(out, t);
        out << std::get<N - 1>(t) << ")";
    }
};

template <typename... Args>
ostream& operator << (ostream& out, const tuple<Args...> t)
{
    PrintHelper<tuple_size<decltype(t)>::value >::print(out, t);
    return out;
}

template<typename T>
struct _cast_helper
{
    T operator() (stringstream& ss) {
        T result;
        ss >> result;
        return result;
    }
};

template<>
struct _cast_helper<string>
{
    string operator() (stringstream& ss) {
        return ss.str();
    }
};

template<typename R, typename T>
R _sstream_cast(const T& o) {
    stringstream ss;
    ss << o;
    return _cast_helper<R>()(ss);
}

template<typename T>
vector<T> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<T> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        if(isdelim) {
            if(e != b || !drop_empty) {
                result.emplace_back(_sstream_cast<T>(string(&s[b], &s[e])));
            }
            state = 0;
            e = b = i + 1;
        } else if(isspace) {
            if(state == 0) {
                e = b = i + 1;
            }
        } else {
            state = 1;
            e = i + 1;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

typedef vector<int> vi;
typedef vector<vi> vvi;
vi make_vi(const string& s) {return split<int>(s, ",", "[] ", true);}
vvi make_vvi(const string& s) { vvi r; for(auto e : split<string>(s, "[]", ", ", true)) r.emplace_back(make_vi(e)); return r;}

/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


#define cout cout

int _main_();
int main() {
    std::thread th1([](){this_thread::sleep_for(chrono::seconds(3));cerr << "!!!Timeout!!!" << endl;exit(1);});
    th1.detach();
    return _main_();
}

发表于 更新于 分类于 Valine： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

今天在B站看到一个视频《斐波那契数列，全网最优解》，UP主给出了求解斐波那契数列通项公式的推导思路。

因为我早年也对这种数列有过研究，而且记得一个更简单的解法，所以记录一下。

斐波那契数列是这样一种数列：

a(1) = a(2) = 1

a(n) = a(n-1) + a(n-2), n>=2

上面是通过递推公式的形式给出的定义，我们注意到递推公式是前两项的线性组合。而线性变换可以通过矩阵表示，我们不妨转换思路来求向量

(an,an+1)(a_n, a_{n+1})

的通项公式

我们写出根据a(n-1), a(n)推得a(n), a(n+1)的递推公式

{an=anan+1=an−1+an\begin{cases} a_n = a_n \\ a_{n+1} = a_{n-1} + a_n \end{cases}

写成矩阵的形式

(anan+1)=(an−1an)[0111]\begin{pmatrix}a_n & a_{n+1} \\ \end{pmatrix} = \begin{pmatrix}a_{n-1} & a_n \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}

我们可以看到这就类似等比数列的递推公式，只不过公比q是个矩阵，等比数列通项公式是

an=a1∗qn−1a_n = a_1 * q^{n-1}

类比得到，上面递推公式的通项公式

(anan+1)=(a1a2)[0111]n−1=(11)[0111]n−1\begin{pmatrix}a_n & a_{n+1} \\ \end{pmatrix} = \begin{pmatrix}a_1 & a_2 \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}^{n-1} = \begin{pmatrix}1 & 1 \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}^{n-1}

BTW: 其实这里矩阵和数还是有点区别的，要利用矩阵乘法有结合律（本来是先做向量和矩阵乘法的，通项公式是先做了后面的矩阵乘法最后再让向量左乘矩阵），而且是方阵才能求幂，而这里都是满足的。

对于斐波那契数列的变形也特别容易推导，无论是改变首项还是改变递推关系，包括把两项和变成前n项的线性组合，只要还是线性的，就可以这么推导。