# 多校联训2(Multi school joint training 2)-其他

## 多校联训2(Multi school joint training 2)

### 我的做法

• 这个数字单独成为一个集合 $$F[i][j][k]\rightarrow F[i – 1][j+1][k+1]$$
• 这个数字和最后面 $$j-k$$ 个和最后一个集合相连的集合连边 $$(j-k)F[i][j][k]\rightarrow F[i-1][j][0]$$
• 这个数字和教后面 $$k$$ 个集合的某个最大数字相连 $$kF[i][j][k]\rightarrow F[i-1][j][k]$$

// 这是我的解法的代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAXN = 505, MOD = 998244353;
/*

f[i][j][k] 为从后向前做到 i 个, 然后已经有 j 个集合，有 k 个集合没有跟 $n$ 那个相连

*/
int N, M, F[2][MAXN][MAXN];
auto Mod = [] (int x) {
if (x >= MOD) {
return x - MOD;
}
else if (x < 0) {
return x + MOD;
}
else {
return x;
}
};
int main() {
freopen("partition.in", "r", stdin);
freopen("partition.out", "w", stdout);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
if (M >= N) {
cout << 0 << '\n';
return 0;
}
F[N & 1][1][0] = 1;
for (int i = N - 1; i; --i) {
int nw = i & 1;
memset(F[nw], 0, sizeof F[nw]);
//不连边，则多一个集合，并且
int num = N - i + 1;
for (int j = 1; j < num && j < M; ++j) {
for (int k = 0; k < j; ++k) {
F[nw][j + 1][k + 1] = Mod(F[nw][j + 1][k + 1] + F[nw ^ 1][j][k]);
}
}
// 连向之前的一个集合和 最后一个集合相连的
for (int j = 1; j <= M && j < num; ++j) {
for (int k = 0; k < j; ++k) {
F[nw][j][0] = ((long long) F[nw ^ 1][j][k] * (j - k) + F[nw][j][0]) % MOD;
}
// 连向之前的 j - k 个集合均可
}
// 和之前一个集合不和最后一个集合相连的相连
for (int j = 1; j < num; ++j) {
for (int k = 1; k < j; ++k) {
F[nw][j][k] = (F[nw][j][k] + (long long) F[nw ^ 1][j][k] * k) % MOD;
}
}
}
cout << F[1][M][0] << '\n';
return 0;
}


### 题意

• 0 pos x 修改 $$A_{pos}$$ 位置的值为 $$x$$。
• 1 l r 查询 $$\varphi (\sum_{i=l}^r A_i)$$
• 2 l r 查询 $$\varphi (\prod _{i=l}^r A_i)$$

$$n\le 5 \times 10^4$$，$$q\le 1\times 10^5$$，$$A_i\le 4\times 10^4$$ 数据完全随机。

### 题解

bitset

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
const int MAXV = 40005, MOD = 1e9 + 7, MAXN = 5e4 + 10;
using std::bitset;
int pri[MAXV], vis[MAXV], idx[MAXV], inv[MAXV], P[MAXV];
bitset<4210> factor[MAXV], ANS;
int N, M, A[MAXN], sc[MAXN];
void print(int x) {
if (x < 10) {
putchar(x + 48);
return;
}
print(x / 10);
putchar(x % 10 + 48);
}
int x = 0;
char ch = getchar();
while (!isdigit(ch)) {
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
struct Node {
long long mul;
bitset<4210> jy;
} nd[MAXN * 4];
#define jy(i) nd[i].jy
#define mul(i) nd[i].mul
inline int ls(int k) {
return k << 1;
}
inline int rs(int k) {
return k << 1 | 1;
}
inline void up(int k) {
mul(k) = mul(ls(k)) * mul(rs(k)) % MOD;
jy(k) = jy(ls(k)) | jy(rs(k));
}
void build(int k, int l, int r) {
if (l == r) {
mul(k) = A[l];
jy(k) = factor[A[l]];
return;
}
int mid = (l + r) / 2;
build(ls(k), l, mid);
build(rs(k), mid + 1, r);
up(k);
}
auto Ksm = [] (int x, int y) -> int {
int ret = 1;
for (; y; y >>= 1, x = (long long) x * x % MOD) {
if (y & 1) {
ret = (long long) ret * x % MOD;
}
}
return ret;
};
void modify(int k, int l, int r, int pos) {
if (l == r) {
mul(k)  = A[pos];
jy(k) = factor[A[pos]];
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
modify(ls(k), l, mid, pos);
}
else {
modify(rs(k), mid + 1, r, pos);
}
up(k);
}
long long query2(int k, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
ANS |= jy(k);
return mul(k);
}
int mid = (l + r) / 2;
long long ret = 1;
if (ql <= mid) {
ret *= query2(ls(k), l, mid, ql, qr);
}
if (mid < qr) {
ret = ret * query2(rs(k), mid + 1, r, ql, qr) % MOD;
}
return ret;
}
void add(int x, int y) {
for (; x <= N; x += x & -x) {
sc[x] += y;
}
}
int query1(int r) {
int ret = 0;
for (; r; r -= r & -r) {
ret += sc[r];
}
return ret;
}
int main() {
freopen("phi.in", "r", stdin);
freopen("phi.out", "w", stdout);
// INIT
std::ios::sync_with_stdio(0);
for (int i = 2; i < MAXV; ++i) {
if (!vis[i]) {
pri[++pri[0]] = i;
idx[i] = pri[0];
}
for (int j = 1; j <= pri[0] && pri[j] * i < MAXV; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
break;
}
}
}
inv[0] = inv[1] = 1;
for (int i = 2; i < MAXV; ++i) {
inv[i] = (long long) (MOD - MOD / i) * inv[MOD % i] % MOD;
}
for (int i = 1; i <= pri[0]; ++i) {
P[i] = (long long) (pri[i] - 1) * inv[pri[i]] % MOD;
}
for (int i = 1; i < MAXV; ++i) {
int x = i;
for (int j = 1; j <= pri[0] && pri[j] * pri[j] <= x; ++j) {
while (x % pri[j] == 0) {
x /= pri[j];
factor[i].set(j);
}
}
if (x != 1) {
factor[i].set(idx[x]);
}
}
//
for (int i = 1; i <= N; ++i) {
}
build(1, 1, N);
for (int opt, l, r; M--; ) {
if (opt == 0) {
A[l] = r;
modify(1, 1, N, l);
}
else if (opt == 1) {
int ret = query1(r) - query1(l - 1), k = ret;
for (int i = 2; i * i <= k; ++i) {
if (!(k % i)) {
ret -= ret / i;
while (!(k % i)) {
k /= i;
}
}
}
if (k > 1) {
ret -= ret / k;
}
print(ret);
putchar('\n');
}
else {
ANS.reset();
long long ret = query2(1, 1, N, l, r);
for (int i = ANS._Find_first(); i < ANS.size(); i = ANS._Find_next(i)) {
ret = ret * P[i] % MOD;
}
print(ret);
putchar('\n');
}
}
return 0;
}


————————

### meaning of the title

Divide the first \ (n \) positive integers into \ (m \) sets (which should be divided according to the category of the second kind of Stirling number), and then a division is good if and only if there is a circular arrangement of \ (m \). Then find the number of good partitions,

### My approach

We consider the transformation of a problem. We believe that one set \ (a \) can connect edges \ (B \) to another set if and only if, \ (\ max (a) & gt; \Min (b) \), it is easy to find that such an edge is at least unidirectional.

In other words, if we draw all the pictures on these sides, then this picture must be a picture < strong > stronger than the competition picture < / strong >.

All we have to do is find the Hamiltonian circuit in this graph. Some properties of tournaments -_ ZWL – blog Park (cnblogs. Com) the above article talks about the nature of a competition chart.

Then the condition of this Hamiltonian loop is equivalent to that the whole tournament is strongly connected. Consider the same condition on the graph stronger than the tournament graph we obtained above, because the connectivity of this graph must be stronger than the tournament graph. If this thing is strongly connected, but there is no Hamiltonian circuit, it is obviously impossible. Suppose that the left is a strongly connected block, the right is a strongly connected block, and there is a bridge connecting this block in the middle, we can always go to the right block through the other edges of the left connected block, and then come back from the bridge.

So, it is obviously not easy for us to directly calculate the number of strong connected cases of this graph. We are considering a transformation of the problem.

Let’s create the following graph, first arrange the numbers from small to large, then connect the large numbers to the small numbers, and then connect the numbers of the same set to the largest number in the set.

It is not difficult to find that the connectivity of this graph is equal to that of the graph above.

Then we can DP the following figure in order.

Our design status is \ (f [i] [J] [k] \), which means that there are \ (J \) sets from the back to the front \ (\ text {dp} \) to the \ (I \), and then there are \ (K \) sets continuously from the number \ (I \) to the back, which are not connected with the last set (regardless of the connectivity status of these sets). The initial state is \ (f [n] [1] [1] = 1 \)

Then we can transfer \ (I \ rightarrow i-1 \) in the following cases:

• This number becomes a single set \ (f [i] [J] [k] \ rightarrow f [I – 1] [J + 1] [K + 1] \)
• This number is bordered by the last \ (J-K \) set connected to the last set \ ((J-K) f [i] [J] [k] \ rightarrow f [I-1] [J] [0] \)
• This number is connected with a maximum number of the following \ (K \) sets \ (KF [i] [J] [k] \ rightarrow f [I-1] [J] [k] \)

The final answer is \ (f [1] [M] [0] \).

We notice that the space of this solution is \ (O (n ^ 3) \) and the time is also \ (O (n ^ 3) \). We can optimize the space to \ (O (n ^ 2) \) by scrolling the array.

This is a possible and feasible method to solve the first problem discussed by Xiong Zihao of Wuhan foreign language school. However, due to the limitation of knowledge, the last part of the algorithm can not be completed because we have not learned the theory of binary polynomials.

Consider the nature of the solution to the problem of chemical application: the value range cannot be divided into two parts.

If this condition is removed, the answer is obviously \ (\ displaystyle {n \ brace m} \); In addition, consider the inclusion exclusion principle. Let \ (f (I) \) indicate the number of schemes whose value range is divided into \ (I \) parts. What is required is:

Considering solving this \ (f (k) \), the most violent idea is to enumerate a partition of the value range \ (\ {(0, i_1], (i_1, i_1 + i_2], (i_1 + i_2, i_1 + i_2 + i_3], \ dots, (\ dots, n]\} \), where \ (\ sum I = n \). Then enumerate the number of sets divided into, which are \ (j_1, j_2, \ dots, j_k \) and \ (\ sum J = m \). For such a division, the corresponding number of schemes is \ (\ displaystyle \ prod {x = 1} ^ k {i_x \ brace j_x} \). Change the above formula:

The following may require some advanced things such as the inverse of binary polynomials, which I don’t know very well.

// 这是我的解法的代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAXN = 505, MOD = 998244353;
/*

f[i][j][k] 为从后向前做到 i 个, 然后已经有 j 个集合，有 k 个集合没有跟 $n$ 那个相连

*/
int N, M, F[2][MAXN][MAXN];
auto Mod = [] (int x) {
if (x >= MOD) {
return x - MOD;
}
else if (x < 0) {
return x + MOD;
}
else {
return x;
}
};
int main() {
freopen("partition.in", "r", stdin);
freopen("partition.out", "w", stdout);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
if (M >= N) {
cout << 0 << '\n';
return 0;
}
F[N & 1][1][0] = 1;
for (int i = N - 1; i; --i) {
int nw = i & 1;
memset(F[nw], 0, sizeof F[nw]);
//不连边，则多一个集合，并且
int num = N - i + 1;
for (int j = 1; j < num && j < M; ++j) {
for (int k = 0; k < j; ++k) {
F[nw][j + 1][k + 1] = Mod(F[nw][j + 1][k + 1] + F[nw ^ 1][j][k]);
}
}
// 连向之前的一个集合和 最后一个集合相连的
for (int j = 1; j <= M && j < num; ++j) {
for (int k = 0; k < j; ++k) {
F[nw][j][0] = ((long long) F[nw ^ 1][j][k] * (j - k) + F[nw][j][0]) % MOD;
}
// 连向之前的 j - k 个集合均可
}
// 和之前一个集合不和最后一个集合相连的相连
for (int j = 1; j < num; ++j) {
for (int k = 1; k < j; ++k) {
F[nw][j][k] = (F[nw][j][k] + (long long) F[nw ^ 1][j][k] * k) % MOD;
}
}
}
cout << F[1][M][0] << '\n';
return 0;
}


### meaning of the title

Let the number of numbers in \ (1 \ SIM n \) that are coprime with \ (n \) be \ (\ varphi (n) \), then give a \ (n \) positive integer sequence \ (a \), and execute \ (Q \) operations at a time. There are three types of operations.

• The value of 0 POS x modified \ (a {POS} \) position is \ (x \).
• 1 L R query \ (\ varphi (\ sum {I = l} ^ R a _i) \)
• 2 l r 查询 $$\varphi (\prod _{i=l}^r A_i)$$

$$n \ Le 5 \ times 10 ^ 4$$, \ (Q \ le 1 \ times 10 ^ 5 \), \ (a_i \ Le 4 \ times 10 ^ 4 \) data are completely random.

### Problem solution

We consider that because the data is random, we can write some algorithms whose complexity seems completely wrong, but it can ensure the complexity when the data is random.

We consider maintaining the sequence directly with the line segment tree, and then maintaining the interval and interval multiplication.

For our answer to an operation, because the value range is small, the maximum answer is \ (2E9 \) level. We can find its \ (\ varphi \) value every time \ (O (\ sqrt{nv}) \).

In this way, the complexity of each time is \ (O (\ log n + \ sqrt {NV}) \)

We are considering two operations. The answer is obviously big, but we can know from the calculation of \ (\ varphi \), we just need to find each prime factor \ (x \) and multiply it by \ (\ frac{x-1}{x} \).

Therefore, we consider that we can maintain a prime factor of \ (I \) for each bit representation on each segment tree node.

bitset

Because the data is random, this is fast< Strong > we can get that the number of prime factors in \ (4 \ times 10 ^ 4 \) is \ (4203 \), not much

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
const int MAXV = 40005, MOD = 1e9 + 7, MAXN = 5e4 + 10;
using std::bitset;
int pri[MAXV], vis[MAXV], idx[MAXV], inv[MAXV], P[MAXV];
bitset<4210> factor[MAXV], ANS;
int N, M, A[MAXN], sc[MAXN];
void print(int x) {
if (x < 10) {
putchar(x + 48);
return;
}
print(x / 10);
putchar(x % 10 + 48);
}
int x = 0;
char ch = getchar();
while (!isdigit(ch)) {
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
struct Node {
long long mul;
bitset<4210> jy;
} nd[MAXN * 4];
#define jy(i) nd[i].jy
#define mul(i) nd[i].mul
inline int ls(int k) {
return k << 1;
}
inline int rs(int k) {
return k << 1 | 1;
}
inline void up(int k) {
mul(k) = mul(ls(k)) * mul(rs(k)) % MOD;
jy(k) = jy(ls(k)) | jy(rs(k));
}
void build(int k, int l, int r) {
if (l == r) {
mul(k) = A[l];
jy(k) = factor[A[l]];
return;
}
int mid = (l + r) / 2;
build(ls(k), l, mid);
build(rs(k), mid + 1, r);
up(k);
}
auto Ksm = [] (int x, int y) -> int {
int ret = 1;
for (; y; y >>= 1, x = (long long) x * x % MOD) {
if (y & 1) {
ret = (long long) ret * x % MOD;
}
}
return ret;
};
void modify(int k, int l, int r, int pos) {
if (l == r) {
mul(k)  = A[pos];
jy(k) = factor[A[pos]];
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
modify(ls(k), l, mid, pos);
}
else {
modify(rs(k), mid + 1, r, pos);
}
up(k);
}
long long query2(int k, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
ANS |= jy(k);
return mul(k);
}
int mid = (l + r) / 2;
long long ret = 1;
if (ql <= mid) {
ret *= query2(ls(k), l, mid, ql, qr);
}
if (mid < qr) {
ret = ret * query2(rs(k), mid + 1, r, ql, qr) % MOD;
}
return ret;
}
void add(int x, int y) {
for (; x <= N; x += x & -x) {
sc[x] += y;
}
}
int query1(int r) {
int ret = 0;
for (; r; r -= r & -r) {
ret += sc[r];
}
return ret;
}
int main() {
freopen("phi.in", "r", stdin);
freopen("phi.out", "w", stdout);
// INIT
std::ios::sync_with_stdio(0);
for (int i = 2; i < MAXV; ++i) {
if (!vis[i]) {
pri[++pri[0]] = i;
idx[i] = pri[0];
}
for (int j = 1; j <= pri[0] && pri[j] * i < MAXV; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
break;
}
}
}
inv[0] = inv[1] = 1;
for (int i = 2; i < MAXV; ++i) {
inv[i] = (long long) (MOD - MOD / i) * inv[MOD % i] % MOD;
}
for (int i = 1; i <= pri[0]; ++i) {
P[i] = (long long) (pri[i] - 1) * inv[pri[i]] % MOD;
}
for (int i = 1; i < MAXV; ++i) {
int x = i;
for (int j = 1; j <= pri[0] && pri[j] * pri[j] <= x; ++j) {
while (x % pri[j] == 0) {
x /= pri[j];
factor[i].set(j);
}
}
if (x != 1) {
factor[i].set(idx[x]);
}
}
//
for (int i = 1; i <= N; ++i) {
}
build(1, 1, N);
for (int opt, l, r; M--; ) {
if (opt == 0) {
A[l] = r;
modify(1, 1, N, l);
}
else if (opt == 1) {
int ret = query1(r) - query1(l - 1), k = ret;
for (int i = 2; i * i <= k; ++i) {
if (!(k % i)) {
ret -= ret / i;
while (!(k % i)) {
k /= i;
}
}
}
if (k > 1) {
ret -= ret / k;
}
print(ret);
putchar('\n');
}
else {
ANS.reset();
long long ret = query2(1, 1, N, l, r);
for (int i = ANS._Find_first(); i < ANS.size(); i = ANS._Find_next(i)) {
ret = ret * P[i] % MOD;
}
print(ret);
putchar('\n');
}
}
return 0;
}


In the actual implementation, because it may be a little stuck, we can consider replacing the summation line segment tree with a tree array.