0%

​ 开个坑,准备把《具体数学》这本书好好学一下。

​ 所以这个帖子被我置顶了,时刻警示着我是个带菜鸡。

阅读全文 »

Rt,博主是个大菜鸡,有什么问题尽管提出。


反演的基本概念

当有这么一个式子的时候:

并且这个 $\mu$ 还很常见,那有一定概率就可以反演。

反演就是,你找出另一个函数 $a$,使得

我们不妨探寻一下这两个表达式间的规律:

接着引入艾弗森括号的概念,即 $[a]$ 这个东西表示若 $a$ 为真,则为 $1$,否则为 $0$。

容易发现,当后面那坨红的恰好等价于 $[n = d]$ 的时候,这个反演的式子就对了。

然后你冷静一下,发现 $a$ 本质上就是 $\mu$ 矩阵的逆矩阵。所以少数情况下你可以打一个 $\mu$ 的表,然后矩阵求逆求出来 $a$,观察到一定规律。

不过鉴于我不会矩阵求逆,并且也没做到那样的题,就先不写了,到时候遇到了再写。


二项式反演

首先有一个前置知识,二项式定理。

组合意义比较显然,就是每个括号决策一下,就不细究了。

然后还有就是 $0^n$ 这个东西显然就是艾弗森括号,想一想能不能通过上面那个东西搞出来 $0^n$?显然是可以的。我们代入 $a = 1, b = -1$,可以得到下面这个式子:

然后我们本质上就是用和式造出来了一个艾弗森括号,于是就可以搞这样一类反演式子:

推这种式子有一个技巧,就是令 $g_n = \sum_{d} [n = d] g_d$,然后探索出一些牛逼的东西。里面那个东西可以变成 $[n - d = 0]$ ,比如说这个例子:

wee,整完了。

再来一个对称美的式子:

证明的话。。。好像把系数拎出来,整一下就ok了。


子集反演

其实道理都是异曲同工的。

首先考虑上面我们推得的二项式艾弗森括号,如何把他推广到子集中?

从展开角度来讲,就是

这里 $ = 0$ 代表空集。

为什么有这个式子?你可以理解为,上面的二项式反演就是对这个式子算贡献。

所以,我们就可以利用这样的思路解决子集反演:

同样的,还是用那个套路:

两个红色式子都比较重要,不过不难推导。

当然还有一个反方向的子集反演,式子很一致。


多重集反演

和上面的子集反演差不多一致,主要区别在于集合变成了多重集,枚举集合变成了枚举本质不同的集合

很自然的想到:如何把多重集反演变成子集反演?只需要设计一个 $\mu(S)$ 函数,设 $S$ 包含相同元素时为 $0$ ,否则为 $(-1)^S$,然后就又变成了上面的情况。

然后类似于上面的反演,就有


莫比乌斯反演

和多重集反演完全一致,就是一个在唯一分解上的多重集反演。

这里注意,基本上所有反演子集和反演超集都是对称的。所以还有这么一个莫比乌斯反演式子(比较不常见):


莫比乌斯反演小题

Crash的数字表格:

(默认 n <= m)
推,就硬推。

注意 $calc$ 是 $1 + 2 + … + x$。

然后继续整活,设 $dt = T$ ,换掉,这一步的目的是让后面的calc能够整除分块:

你发现这题如果你能快速算出后面那坨,你就会像ei一样直接把这个题秒掉。

事实上的确是可以的,就是一个 $\text{Dirichlet}$ 前缀和。

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
const int N = 10001000;
const int mod = 20101009;
const int inv2 = 10050505;
template<class T> T add(T a, T b) { return a + b >= mod ? a + b - mod : a + b; }

ll calc(int x) { return (ll)x * (x+1) % mod * inv2 % mod; }
bool np[N];
int prime[N], cnt, mu[N], prefix[N], ans[N], n, m;
void init(int sz) {
mu[1] = 1, np[1] = 1;
F(i, 2, sz) {
if (!np[i]) prime[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * prime[j] <= sz; ++j) {
np[i * prime[j]] = 1;
if (i % prime[j]) mu[i * prime[j]] = -mu[i];
else { mu[i * prime[j]] = 0; break; }
}
}
F(i, 1, sz) ans[i] = (mu[i] * i % mod + mod) % mod;
F(i, 1, cnt)
for(int j = 1; prime[i] * j <= sz; ++j)
ans[j * prime[i]] = add(ans[j * prime[i]], ans[j]);
}
void solve() {
cin >> n >> m;
if (n > m) swap(n, m);
init(m);
ll answer = 0;
F(T, 1, n)
answer = add(answer, (ll)T * calc(n/T) % mod * calc(m/T) % mod * ans[T] % mod);
cout << answer << endl;
}

懒得改成根号版本了,反正就几行的事情。

欧拉心算:求

推,就硬推。

啊哈!后面的东西是个卷积!然后你就令人窒息的发现你不会了。

这里有一个性质:一个能筛的函数和 $\mu,\phi$ 卷一下,仍然能筛。所以搞一下后面那个函数即可。

upd: 来表演一下不欧拉筛, $O(n \log n)$ 过这个题。

upd: flag倒了,时限卡的太死了。

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
#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define F(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define endl '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


const int N = 10000010;
int mu[N], phi[N], prime[N], cnt;
ll sum[N];
bool nprime[N];
void init() {
nprime[1] = 0;
mu[1] = phi[1] = 1;
F(i, 2, N-1) {
if (!nprime[i]) prime[++cnt] = i, mu[i] = -1, phi[i] = i - 1;
for(int j = 1; j <= cnt && i * prime[j] < N; ++j) {
nprime[i * prime[j]] = 1;
if (i % prime[j]) mu[i * prime[j]] = -mu[i], phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
mu[i * prime[j]] = 0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
F(i, 1, N-1)
for(register int j = i, val = 1; j <= N-1; j += i, ++val)
sum[j] += phi[i] * mu[val];
F(i, 1, N-1) sum[i] += sum[i - 1];
}



void solve() {
int n;
cin >> n;
ll ans = 0;
for(int l = 1, r; l <= n; l++) {
r = n / (n / l);
ans += (sum[r] - sum[l-1]) * (n/l) * (n/l);
l = r;
}
cout << ans << endl;
}

int main() {
ios::sync_with_stdio(false);
cout << fixed;

#ifdef LOCAL
double cl = clock();
#endif

init();
int T = 1;
cin >> T;
while (T--) solve();

#ifdef LOCAL
cerr << "Time elapsed: " << (clock() - cl) / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}

$\text{C}$

看到 $m \leq 1000$,就会收到一个很明显的提示,即可以直接枚举答案。

枚举差之后计算一下个数,快速幂一下就行了。

当然如果你脑回路正常,会意识到根据鸽巢原理,当 $n > m$ 的时候答案一定是 $0$(因为一定有两个数同余),其余情况暴力即可。

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
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int mod;
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }
inline int add (int a, int b) { return a + b >= (mod - 1) ? a + b - (mod - 1) : a + b; }
inline int circ (int x) { while (x >= mod) x -= mod; return x; }
const int N = 202000;
int n, a[N], pric[N];
unordered_map <int, int> p;
int main() {
n = read(), mod = read();
if (n > mod) return puts("0"), 0;
for (int i = 1; i <= n; ++i) a[i] = read();
ll ans = 1;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
ans = ans * abs(a[i] - a[j]) % mod;
cout << ans << '\n';
return 0;
}

$\text{D}$

很好的一道构造题。

对于每步询问,我们都去询问两个度数为 $1$ 的点。这样有一个好处:如果他们两个的 $\text{LCA}$ 就是其一,那么是 $\text{LCA}$ 的那个点就是根(这个性质画图显然),否则我们就可以直接把这两个叶子删掉,牵出新的叶子。

这样如果每次没找到答案,最后一定至少没了两个点,所以最后一定能找到解。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 100010;
int n, r, x[N], y[N], d[N], banned[N];
vector <int> g[N];
int main() {
n = read();
rep (i, 1, n - 1) {
x[i] = read(), y[i] = read();
d[x[i]]++, d[y[i]]++;
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
set <int> st;
rep (i, 1, n) st.insert(i);
while (true) {
if (st.size() == 1) return cout << "! " << *(st.begin()) << endl, 0;
vector <int> v;
rep (i, 1, n) if (d[i] == 1) v.push_back(i);
assert(v.size());
if (v.size() < 2) return cout << "! " << v[0] << endl, 0;
cout << "? " << v[0] << " " << v[1] << endl;
int lca = read();
if (lca == v[0] || lca == v[1]) return cout << "! " << lca, 0;
else {
st.erase(v[0]), st.erase(v[1]);
rep (i, 1, n - 1) if (x[i] == v[0] || x[i] == v[1] || y[i] == v[0] || y[i] == v[1]) {
if (!banned[i]) banned[i] = 1, --d[x[i]], --d[y[i]];
}
}
}
return 0;
}

$\text{E}$

挺神仙的

考虑如果我们要构造尽可能多的答案该如何去构造:直接构造 $1, 2, 3…x$ 即可。

但是如果这样构造到一个地方多了怎么办呢?令当前和为 $cnt$,那我们让当前这个数加上 $2\times (cnt - m)$ ,一定满足条件。

最后补齐就用一定间隔的最大的数即可,这样对答案没有贡献。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 5050;
int n, m, a[N], answer[N];
int main() {
cin >> n >> m;
int now = 0;
for (int i = 1; i <= n; ++i) {
now += (i - 1) / 2;
answer[i] = i;
if (now >= m) {
int dt = now - m;
answer[i] += 2 * dt;
for (int j = n, num = 1e9; j > i; j--, num -= answer[i] + 1)
answer[j] = num;
rep (j, 1, n) printf("%d ", answer[j]);
return 0;
}
}
puts("-1");
return 0;
}