莫比乌斯反演与容斥原理

退役前一直想把莫比乌斯反演与容斥原理统一在一起,奈何自己水平不足,只能作罢。
这次把《组合数学》、《具体数学》、《初等数论》的相关内容读了一遍,总算是完成了这个遗愿:
mobius_and_inclusion_exclusion_principle

Download:https://oi.qizy.tech/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf
拓展阅读1:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
拓展阅读2:http://vfleaking.blog.uoj.ac/blog/87

Latex入门文档

很久没用latex写过东西了,再加上编辑器从Emacs换成了VScode,于是为了写下面↓那个slide就找了点资料熟悉一下。
找到了这一份:https://liam0205.me/2014/09/08/latex-introduction/
感觉写得很好,而且作者似乎是CTeX的主要维护者之一?大力推荐啊!

然后这是我这次用到的一些命令,在这里存个档:

1. insert a picture
\usepackage{graphicx}
\graphicspath{{./figs/}}
\includegraphics[width=100pt]{vfk}

2. 居中
\begin{center}
\end{center}

3. 字号
\tiny
\scriptsize
\footnotesize
\small
\normalsize
\large
\Large
\LARGE
\huge
\Huge

4. buff
\textbf{文字}
\emph{文字}

5. 换页
\clearpage
\newpage

6. 原样输出
\begin{verbatim}
\end{verbatim}

7. gif
\usepackage{animate}
\animategraphics[loop,autoplay,width=200pt]{12}{blo-}{0}{119}

8. 段落缩进
\usepackage{indentfirst}
\setlength{\parindent}{\ccwd}

9. beamer暂停
\pause

10. 行间距调整
\vspace{10pt}

11. 多行公式
$\begin{aligned}
  \sum\limits_{i = 1}^{n}{k \mod i} & = \sum\limits_{i = 1}^{n}{(k - \lfloor \frac{k}{i} \rfloor \cdot i)} \\
  & = n \cdot k - \sum\limits_{i = 1}^{n}{\lfloor \frac{k}{i} \rfloor \cdot i}
\end{aligned}$
带编号的话就去掉"ed"
单行不带编号:\notag

12. 列表
\usepackage{enumerate}
\begin{enumerate}[1.]
  \item 
\end{enumerate}

13. 插入链接
\href{https://233.com}{233}

14. 分栏
\usepackage{multicol}
\begin{multicols}{3}
  \tableofcontents
\end{multicols}

15. 公式编号
\begin{equation}
  233 = 233
\end{equation}

16. 文章内引用
\begin{equation}
  233
  \label{convolution}
\end{equation}
\eqref{convolution}

17. 空格
\qquad
\quad

18. 取模
$a^{n!} \pmod{p}$

19. 证毕
\qed

20. 整段缩进
\begin{enumerate}[\hspace{15mm}]
  \item 666

  \item 233
\end{enumerate}

21. 反斜杠
\usepackage{slashed}
$\slashed{\le}$

22. 数学公式字体大小
\textstyle{233}
\displaystyle
\scriptstyle
\scriptscriptstyle

【Tricks】Hello World!

之前见过这货的低配版
也是全部define成_,然后搞

但今天看到这货,用了define能组合的特点
真的是变态啊_(:з」∠)_

#define _________ }  
#define ________ putchar  
#define _______ main  
#define _(a) ________(a);  
#define ______ _______(){  
#define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C)  
#define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F)  
#define ____ _(0x72)_(0x6C)_(0x64)_(0x21)  
#define _____ __ ___ ____ _________  
#include<stdio.h>  
_____

【Python】qCleaner

背景

大家存比赛的时候一般都会把源码一起存下来
但有些同学交源码之前喜欢编译一下
于是就有很多废的.exe文件
而且这些文件大小都在$1M$以上,所以占用了极大的空间

qCleaner

于是我就用Python写了一个小工具
大概就长这样啦:

我知道很丑

它会递归扫描指定目录下的所有目录
然后每找到一个.cpp文件就会在同一个目录下查找同名.exe文件
如果存在的话,就会把同名.exe文件删掉

怎么样?是不是很贴心?
我大概用这货删掉了快$2G$的.exe文件吧!

获取与使用

  1. 打开https://github.com/yongzhengqi/qCleaner/releases
  2. 下载qCleaner.zip并解压
  3. 双击qCleaner即可打开程序
  4. 手动输入路径,或者点击浏览来选择路径。之后点击清理即可

为什么不用脚本

  1. qCleaner有可视化界面,便于使用
  2. qCleaner可以实时显示清理进度,也可以随时强行终止
  3. 我编不出来了qwq

后记

总之,qCleaner作为我正式写的第一个Python程序,我还是很满意的
而且这货的GUI是用的PyQt,所以还有很大的提升空间

嗯,大概就这样了吧
这可能是我退役前写的第一个也是最后一个自己想写的程序了吧

【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817

解题报告

我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数

于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M]; 
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LOG - 1; ~j; j--) {
		if (dep[ff[u][j]] >= dep[v]) {
			u = ff[u][j];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LOG - 1; ~j; j--) {
		if (ff[u][j] != ff[v][j]) {
			u = ff[u][j];
			v = ff[v][j];
		}
	}
	return ff[u][0];
}

class SegmentTree{
	int root, ch[M][2], tag[M], mx[M];
public:
	inline void init() {
		build(root, 1, n);
	}
	inline void modify(int l, int r, int d) {
		modify(root, 1, n, l, r, d);
	}
	inline int query(int l, int r = -1) {
		return query(root, 1, n, l, r >= 0? r: l);
	}
private:
	inline void PushDown(int w) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			mx[ls] += tag[w];
			mx[rs] += tag[w];
			tag[ls] += tag[w];
			tag[rs] += tag[w];
			tag[w] = 0;
		}
	}
	inline int query(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return mx[w];
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) {
				ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
			}
			if (mid <= R) {
				ret = max(ret, query(ch[w][1], mid, r, L, R));
			}
			return ret;
		}
	}
	inline void modify(int w, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			tag[w] += d;
			mx[w] += d;
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				modify(ch[w][0], l, mid - 1, L, R, d);
			}
			if (mid <= R) {
				modify(ch[w][1], mid, r, L, R, d);
			}
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			mx[w] = dep[num[l]];
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
}SGT;

class LinkCutTree{
	int ch[N][2], fa[N];
public:
	inline void SetFather(int w, int f) {
		fa[w] = f;
	}
	inline void access(int x) {
		for (int last = 0; x; last = x, x = fa[x]) {
			splay(x);
			if (fa[x]) {
				int p = GetMin(x);
				SGT.modify(in[p], ot[p], -1);
			}
			if (ch[x][1]) {
				int p = GetMin(ch[x][1]);
				SGT.modify(in[p], ot[p], 1);
			}
			ch[x][1] = last;
		}
	}
private:
	inline bool IsRoot(int x) {
		return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
	}
	inline int GetMin(int x) {
		return ch[x][0]? GetMin(ch[x][0]): x;
	}
	inline void splay(int x) {
		for (int f, ff; !IsRoot(x); ) {
			f = fa[x], ff = fa[f];
			if (IsRoot(f)) {
				rotate(x);
			} else {
				if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
					rotate(x);
					rotate(x);
				} else {
					rotate(f);
					rotate(x);
				}
			}
		}
	}
	inline void rotate(int x) {
		int f = fa[x], t = ch[f][1] == x;
		fa[x] = fa[f];
		if (!IsRoot(f)) {
			ch[fa[f]][ch[fa[f]][1] == f] = x;
		}
		ch[f][t] = ch[x][t ^ 1];
		fa[ch[x][t ^ 1]] = f;
		ch[x][t ^ 1] = f;
		fa[f] = x;
	}
}LCT;

inline void DFS(int w, int f) {
	static int ID = 0;
	LCT.SetFather(w, f);
	ff[w][0] = f;
	dep[w] = dep[f] + 1;
	num[in[w] = ++ID] = w;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	ot[w] = ID;
}	

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	DFS(1, 0);
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= n; i++) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	SGT.init();
	for (int i = 1; i <= m; i++) {
		int opt = read();
		if (opt == 1) {
			LCT.access(read());
		} else if (opt == 2) {
			int u = read(), v = read(), lca = LCA(u, v);
			printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
		} else {
			int x = read();
			printf("%d\n", SGT.query(in[x], ot[x]));
		}
	}
	return 0;
}

【BZOJ 4589】Hard Nim

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

解题报告

我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}