THC

WIKI

0%

PtzCamp Tutorial

Posted on Edited on

毛营做题记录

Day5

D. Two Missing Numbers

见 \(\text{Nimber}\) 。

G. Good and Lucky Matrices

题意

对于一个 \(n\times n(n\le2000)\) 的 \(01\) 矩阵 \(A\) ，我们称其为：

  • good 当 \(\det A\) 为奇数
  • lucky 当以下的贪心匹配算法成功找到一个匹配。该算法依次按行从上往下读入矩阵，如果该行有一列为 \(1\) 且从未选择过，则选择最左边的符合条件的那一列。

你需要构造一个 good 和 lucky 矩阵之间的双射，给定某一矩阵你的程序需要输出与之对应的另一矩阵。

题解

人类智慧题。

考虑 good 矩阵个数。我们只关心行列式的奇偶性，于是可以将所有元素模 \(2\) ，那么高斯消元求行列式中的加法就可以被换成异或，那么自然可以得到 \(01\) 矩阵的行列式为奇数当且仅当 \(n\) 行在异或运算意义下线性独立。考虑从上往下构造符合条件的矩阵，每行都不能在上面的行组成的线性空间中，故共有 \((2^n-2^0)\cdot(2^n-2^1)\cdots(2^n-2^{n-1})\) 个这样子的矩阵。

考虑 lucky 矩阵个数。那么第一行至少有一个 \(1\) ，被钦定的那列和第一行之后都不会再修改，就相当于移除出的这个矩阵，于是变成了 \((n-1)\times (n-1)\) 矩阵的子问题。考虑一个 \(n\times n\) 矩阵钦定第一行的方案数，被钦定的那个位置的右边和下边可以随意放，左边为 \(0\) ，故方案数为 \(2^{n-1}\cdot\sum\limits_{i=1}^n2^{n-i}=(2^n-1)\cdot2^{n-1}\) 。于是总方案数为 \((2^n-1)\cdot2^{n-1}\cdot(2^{n-1}-1)\cdot2^{n-2}\cdots(2-1)\cdot2^0\) 。

我们惊奇地发现这两个数是相等的。

考虑如何构造双射。有个神仙思路。

good 转 lucky：跑高斯消元，但是不换行，而是对于某行 \(i\) 找到第一个没有使用过的列 \(j\) 且 \(A_{i,j}=1\) 。然后将 \(\forall k, A_{i,k}\) 和 \(\forall r>i,A_{r,j}\) 按原位置记录到答案数组中。然后 \(\forall r>i, A_{r,j}=1\) 的行 \(r\) ，使 \(A_r=A_i\oplus A_r\) ，这不影响答案数组中的值。显然得到的答案矩阵是 lucky 矩阵。

lucky 转 good：倒着做上述的高斯消元，由于我们的设计这个过程是可逆的。

Code

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
const int N = 2100;
int n;
bitset<2100> a[N], b[N], used;
void solve() {
	string s; cin >> s;
	cin >> n; used = 0;
	for(int i = 1; i <= n; i++) {
		string t; cin >> t;
		for(int j = 1; j <= n; j++) {
			a[i][j] = t[j - 1] - '0';
		}
	}
	if(s == "lucky") {
		vi local(n + 1, 0);
		for(int i = 1; i <= n; i++) {
			b[i] = a[i];
			for(int j = 1; j <= n; j++)
				if(!used[j] && a[i][j]) {
					local[i] = j;
					used[j] = 1;
					break;
				}
		}
		used = 0;
		for(int i = n; i >= 1; i--) {
			int p = local[i]; used[p] = 1;
			for(int j = i + 1; j <= n; j++)
				if(a[j][p]) b[j][p] = 0, b[j] ^= (b[i] & used);
		}
	} else {
		for(int i = 1; i <= n; i++) {
			int p;
			for(int j = 1; j <= n; j++)
				if(a[i][j]) { p = j; break; }
			for(int j = 1; j <= n; j++)
				if(!used[j]) b[i][j] = a[i][j];
			used[p] = 1;
			for(int j = i + 1; j <= n; j++)
				b[j][p] = a[j][p];
			for(int j = i + 1; j <= n; j++)
				if(a[j][p]) a[j] ^= a[i];
		}
	}
	cout << n << '\n';
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++)
			cout << b[i][j];
		cout << '\n';
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _; cin >> _; for(int cas = 1; cas <= _; cas++) solve();
	return 0;
}t

Day6

H. Exact Subsequences

题意

求出字典序第 \(k\le10^9\) 小的包含 \(n\le10^9\) 个本质不同子序列的01字符串，多测 \(T\le 100\) 。

题解

考虑给定01字符串如何求出其有几个本质不同子序列，有两种设计dp的方式。

Way1：令 \(f_i\) 表示以字符串第 \(i\) 位结尾的子序列个数，转移为 \(f_i\rightarrow f_{nxt_0},f_{nxt_1}\) ，答案为 \(\sum f_i\) 。这个dp式子不够优美，故不讨论。

Way2：令 \(f_{0/1}\) 表示以0/1结尾的子序列个数，记 \([a,b]\) 为状态，逐一扫描原串加入字符， \(a\) 存以1结尾个数。初始状态 \([0,0]\) ，加入1转移为 \([a,b]\rightarrow[a+b+1,b]\) ，加入0转移为 \([a,b]\rightarrow[a,a+b+1]\) ，其中 \(+1\) 来自空串往后加0/1。终态答案为 \(a+b+1\) 。

我们发现 \(a+b+1\) 中有个 \(+1\) 很难看，于是人为把 \([a,b]\rightarrow[a+1,b+1]\) ，这个时候我们发现转移为 \([a,b]\rightarrow[a+b,b]\ or\ [a,a+b]\) ，是一个辗转相除的形式。这个状态设计有一个性质为 \([a,b]\) 一一对应一个字符串，因为你可以倒着把那个字符串构造出来。

由于二元组与字符串一一对应，于是我们可以只考虑有哪些 \([a,b]\) 满足 \(a+b=n+2\) ，且又由于 \([a,b]\) 是由 \([1,1]\) 逐步构造出来的，那么必有 \(\gcd(a,b)=1\) ，发现这个就是欧拉函数的定义，于是不同子序列个数为 \(n\) 的字符串总数为 \(\varphi(n+2)\) 。并且第 \(k\) 小的字符串就是与 \(n+2\) 互质的数中的第 \(k\) 小的数。

考虑二分求出该数，需要求：

\[ \sum_{i=1}^{mid}[\gcd(n,i)=1] =\sum_{i=1}^{mid}\sum_{d|n,i}\mu(d) =\sum_{d|n}\mu(d)\sum_{i=1}^{\lfloor\frac{mid}{d}\rfloor}1 =\sum_{d|n}\mu(d)\left\lfloor\frac{mid}{d}\right\rfloor \]

于是直接二分完后反向构造出答案即可。总复杂度为 \(O(T\sqrt{n}\log n)\) 。

有一点小trick就是不需要求出 \(n\) 的所有的因子，只需要求指数 \(\le1\) 的因子就可以，因为指数 \(>1\) 的时候 \(\mu=0\) 没有贡献。

Code

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
int n, k;
vector<pii> d, factor; vi ans;
int phi(int n) {
    int res = n; d.clear();
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) {
            int e = 0;
            res = res / i * (i - 1);
            while(n % i == 0) n /= i, e++;
            d.pb(Mp(i, e));
        }
    if(n != 1) res = res / n * (n - 1), d.pb(Mp(n, 1));
    return res;
}
void getFactor(int x, int nw = 1, int mu = 1) {
    if(x == SZ(d)) return factor.pb(Mp(nw, mu)), void();
    for(int i = 0; i <= 1; i++)
        getFactor(x + 1, nw, mu * (i ? -1 : 1)), nw *= d[x].fi;
}
int calc(int m) {
    int res = 0;
    for(auto [d, mu] : factor) res += mu * (m / d);
    return res;
}
void solve() {
    scanf("%d %d", &n, &k); n += 2;
    if(phi(n) < k) return puts("-1"), void();
    factor.clear(), getFactor(0);
    int l = 1, r = n - 1, m;
    while(l < r) {
        m = l + r >> 1;
        if(calc(m) < k) l = m + 1;
        else r = m;
    }
    ans.clear(); int a = l, b = n - l;
    while(a != 1 || b != 1) {
        if(a == 1) ans.pb(b - 1), b = 1;
        else if(b == 1) ans.pb(a - 1), a = 1;
        else if(a > b) ans.pb(a / b), a %= b;
        else ans.pb(b / a), b %= a;
    }
    printf("%d %d\n", SZ(ans), 2 * l < n ? 0 : 1);
    for(int i : ans) printf("%d ", i); puts("");
}
signed main() {
    int _; scanf("%d", &_); for(int cas = 1; cas <= _; cas++) solve();
    return 0;
}

I. SPPPSPSS.

题意

给定长度 \(n\le10^6\) 排列，第 \(i\) 次操作选择前 \(i\) 个或后 \(i\) 个排序，问最少几次能够将整个序列排序，输出方案形如"SPPPSPSS."第 \(i\) 个字母是S表示对后缀操作，为P表示对前缀操作。

题解

显然SP交错至少比SS或PP不劣。然后我们分两种情况分析：

S和P的作用区间没有交叉。这种情况比较好分析，至多操作 \(\frac{n}{2}\) 次后会变成下一种情况。总排序的个数位 \(O(n)\) 。

S和P的作用区间有交叉。不妨对S考虑，每次对S操作都会把P的末尾抢到S中（实际上后面的元素被抢过去后就排好了序），然后把S中的小数在下次操作时还给P。我们发现每次操作，抢过来的元素都会比上一次多2，这意味着我们排序的效率也是每次多2，那么我们可以在至多 \(\sqrt{n}\) 次操作内将整个序列排好序。而且还有一点观察就是在左右交换的元素个数是 \(O(n)\) 的，因为 \(\frac{\sqrt{n}(\sqrt{n}+1)}{2}=O(n)\) 。

于是我们可以开两个priority_queue来存错左边和右边的值，由于总排序的个数为 \(O(n)\) 于是总复杂度就是 \(O(nlogn)\) 。

Code

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
const int N = 1000100;
int n, a[N], v[N];
int go() {
    int l = 1, r = n + 1;
    priority_queue<int> lhs; lhs.push(a[1]);
    priority_queue<int, vi, greater<int>> rhs;
    for(int i = 2, to; i <= n; i++) {
        if(i % 2) { // left
            to = l + 2;
            while(SZ(lhs) < to) {
                if(l < to) l++;
                if(l < r) lhs.push(a[l]);
                else lhs.push(rhs.top()), rhs.pop();
            }
            if(lhs.top() == l && (l >= r || v[r - 1] - v[l] == r - l - 1))
                return i;
        } else { // right
            to = r - 2;
            while(SZ(rhs) < n - to + 1) {
                if(r > to) r--;
                if(l < r) rhs.push(a[r]);
                else rhs.push(lhs.top()), lhs.pop();
            }
            if(rhs.top() == r && (l >= r || v[r - 1] - v[l] == r - l - 1))
                return i;
        }
    }
}
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v[i] = (a[i] == i) + v[i - 1];
    }
    if(v[n] == n) return puts("."), 0;
    int ans0 = go();
    reverse(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) {
        a[i] = n - a[i] + 1;
        v[i] = (a[i] == i) + v[i - 1];
    }
    int ans1 = go();
    if(ans0 < ans1) {
        for(int i = 1; i <= ans0; i++)
            putchar(i % 2 ? 'P' : 'S');
        puts(".");
    } else {
        for(int i = 0; i < ans1; i++)
            putchar(i % 2 ? 'P' : 'S');
        puts(".");
    }
    return 0;
}

Day7

C. Classical Data Structure Problem

题意

\(n\le 5\cdot10^5\) 次操作，第 \(i\) 次操作给定 \(0\le l,r<2^m,1\le m\le 30\) ，将 \(a_l\sim a_r\) 加上 \(i\) ，并使 \(x\gets x+\sum_l^ra_i\) ，求所有操作完成后 \(x\bmod 2^{30}\) 的值。强制在线， \(3s-128MB\) 。

题解

注意到空间限制很紧，不能动态开点线段树等对空间要求为 \(O(n\log A)\) 的数据结构，故考虑平衡树维护区间。

Code

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
const int N = 500100;

struct node {
	int l, r, lc = -1, rc = -1, p, h = 0;
	uint sum = 0, add = 0;
	node(int l_=0, int r_=0, int p_=0) :
		l(l_), r(r_), p(p_) {}
} a[N * 4];
int tot;

int newnode(int l, int r, int p) {
	a[++tot] = node(l, r, p);
	return tot;
}

void rotateRight(int x) {
	int y = a[x].lc;
	if(a[a[x].p].lc == x) {
		a[a[x].p].lc = y;
	} else {
		a[a[x].p].rc = y;
	}
	a[y].p = a[x].p;
	a[a[y].rc].p = x;
	a[x].lc = a[y].rc;
	a[y].rc = x;
	a[x].p = y;
}

void rotateLeft(int x) {
	int y = a[x].rc;
	if(a[a[x].p].lc == x) {
		a[a[x].p].lc = y;
	} else {
		a[a[x].p].rc = y;
	}
	a[y].p = a[x].p;
	a[a[y].lc].p = x;
	a[x].rc = a[y].lc;
	a[y].lc = x;
	a[x].p = y;
}

void push(int x) {
	for(int i = 0; i < 2; i++) {
		int y = i ? a[x].lc : a[x].rc;
		a[y].add += a[x].add;
		a[y].sum += a[x].add * uint(a[y].r - a[y].l);
	}
	a[x].add = 0;
}

void pull(int x) {
	if(a[a[x].lc].h > a[a[x].rc].h + 1) {
		int y = a[x].lc;
		if(a[a[y].rc].h > a[a[y].lc].h) {
			rotateLeft(y);
			pull(y);
		}
		rotateRight(x);
		pull(x);
		pull(a[x].p);
		return;
	}
	if(a[a[x].rc].h > a[a[x].lc].h + 1) {
		int y = a[x].rc;
		if(a[a[y].lc].h > a[a[y].rc].h) {
			rotateRight(y);
			pull(y);
		}
		rotateLeft(x);
		pull(x);
		pull(a[x].p);
		return;
	}
	a[x].l = a[a[x].lc].l;
	a[x].r = a[a[x].rc].r;
	a[x].sum = a[x].add = 0;
	for(int i = 0; i < 2; i++) {
		int y = i ? a[x].lc : a[x].rc;
		a[x].sum += a[y].sum;
	}
	a[x].h = max(a[a[x].lc].h, a[a[x].rc].h) + 1;
}

uint update(int x, int l, int r, uint v) {
	if(l <= a[x].l && a[x].r <= r) {
		a[x].sum += v * uint(a[x].r - a[x].l);
		a[x].add += v;
		return a[x].sum;
	}
	if(a[x].lc == -1) {
		int m = (a[x].l < l && l < a[x].r) ? l : r;
		a[x].lc = newnode(a[x].l, m, x);
		a[x].rc = newnode(m, a[x].r, x);
	}
	push(x);
	uint res = 0;
	if(l < a[a[x].lc].r) {
		res += update(a[x].lc, l, r, v);
	}
	if(r > a[a[x].rc].l) {
		res += update(a[x].rc, l, r, v);
	}
	pull(x);
	return res;
}

int n, m;
signed main() {
	scanf("%d %d", &n, &m);
	int all = 1 << m;
	a[0].lc = newnode(0, all, 0);
	uint ans = 0;
	for(int i = 1; i <= n; i++) {
		uint l, r;
		scanf("%u %u", &l, &r);
		l = (l + ans) & (all - 1);
		r = (r + ans) & (all - 1);
		if(l > r) swap(l, r);
		r++;
		ans += update(a[0].lc, l, r, i);
	}
	printf("%u\n", ans & ((1 << 30) - 1));
	return 0;
}

H. Classical Maximization Problem

题意

二维平面上给定 \(2n\le2\cdot10^5\) 个点，两个点可匹配当且仅当 \(x_i=x_j\lor y_i=y_j\) ，求出最大匹配数及方案。

题解

左转22南京站 J 。

对于一个点我们把左边 \(x\) 点与右边 \(y\) 点连接起来，那么点变成了边，两条边可匹配当且仅当两条边共点，则我们对建出来的图随便跑一个 dfs 树出来后根据深度从深到浅对每个点 \(v\) 上的边做匹配即可，需要注意的是 \(v\rightarrow fa_v\) 这条边是用来补充的，初始不加入，因为需要把没匹配的边往上移才能最优。

Code

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
const int N = 400100;
int n, x[N], y[N], v[N], vv[N];
vector<pii> G[N], ans;
void dfs(int x, int fr, int fe) {
    v[x] = 1; vi es;
    for(auto [y, e] : G[x]) if(y != fr) {
        if(!v[y]) dfs(y, x, e);
        if(!vv[e]) es.pb(e);
    }
    if(SZ(es) % 2 && fe != -1) es.pb(fe);
    for(int i = 1; i < SZ(es); i += 2)
        ans.pb(Mp(es[i - 1], es[i])), vv[es[i - 1]] = vv[es[i]] = 1;
}
void solve() {
    scanf("%d", &n);
    vi X, Y;
    for(int i = 1; i <= 2 * n; i++) {
        scanf("%d %d", &x[i], &y[i]);
        X.pb(x[i]), Y.pb(y[i]), vv[i] = 0;
    }
    sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end()), Y.erase(unique(Y.begin(), Y.end()), Y.end());
    for(int i = 0; i < SZ(X) + SZ(Y); i++)
        v[i] = 0, G[i].clear();
    for(int i = 1; i <= 2 * n; i++) {
        x[i] = lower_bound(X.begin(), X.end(), x[i]) - X.begin();
        y[i] = lower_bound(Y.begin(), Y.end(), y[i]) - Y.begin();
        G[x[i]].pb(Mp(y[i] + SZ(X), i)), G[y[i] + SZ(X)].pb(Mp(x[i], i));
    }
    ans.clear();
    for(int i = 0; i < SZ(X) + SZ(Y); i++) if(!v[i]) {
        dfs(i, -1, -1);
    }
    printf("%d\n", SZ(ans));
    for(auto [i, j] : ans) printf("%d %d\n", i, j);
    for(int i = 1, lst = -1; i <= 2 * n; i++) if(!vv[i]) {
        if(lst != -1) printf("%d %d\n", i, lst), lst = -1;
        else lst = i;
    }
}
signed main() {
    int _; scanf("%d", &_); for(int cas = 1; cas <= _; cas++) solve();
    return 0;
}

J. Classical Scheduling Problem

题意

给定 \(n\le 2\cdot 10^5,t\le10^{14}\) ，有 \(n\) 个任务 \(a_i,b_i\) 一个任务需要 \(a_i\) 的时间，且总共完成 \(b_i\) 个任务这个任务才算完成，问最多能完成几个任务且总耗时不超过时间 \(t\) 。

题解

答案显然有单调性，二分答案，求解是否可以有 \(\ge x\) 个任务完成。

后对所有任务根据 \(b_i\) 排序，然后枚举 \(i\) 前面选择 \(x\) 个任务，除去这 \(x\) 任务再完成 \(b_i-x\) 个任务，显然选最小的最优，于是可以用set等维护，总时间复杂度 \(O(n\log^2n)\) 。

Code

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
const int N = 200100;
int n; ll t; vi ans;
struct node { int fi, se, id; } a[N];
bool chk(int x, int fl = 0) {
    set<pii> lhs, rhs, rest; ll lsum = 0, rsum = 0;
    for(int i = 1; i <= n; i++) rest.insert(Mp(a[i].fi, a[i].id));
    for(int i = 1; i <= n; i++) {
        pii nw = Mp(a[i].fi, a[i].id);
        if(rhs.find(nw) != rhs.end()) rhs.erase(nw), lhs.insert(nw), rsum -= nw.fi, lsum += nw.fi;
        else lhs.insert(nw), rest.erase(nw), lsum += nw.fi;
        while(SZ(lhs) > x) rest.insert(*lhs.rbegin()), lsum -= lhs.rbegin()->fi, lhs.erase(*lhs.rbegin());
        if(i >= x) {
            int req = a[i].se - x;
            while(SZ(rhs) < req) rhs.insert(*rest.begin()), rsum += rest.begin()->fi, rest.erase(rest.begin());
            while(SZ(rhs) && SZ(rest) && rhs.rbegin()->fi > rest.begin()->fi) {
                rest.insert(*rhs.rbegin()), rsum -= rhs.rbegin()->fi, rhs.erase(*rhs.rbegin());
                rhs.insert(*rest.begin()), rsum += rest.begin()->fi, rest.erase(rest.begin());
            }
            if(lsum + rsum <= t) {
                if(fl) {
                    ans.clear();
                    for(auto [w, i] : lhs) ans.pb(i);
                    for(auto [w, i] : rhs) ans.pb(i);
                }
                return true;
            }
        }
    }
    return false;
}
void solve() {
    scanf("%d %lld", &n, &t);
    for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se), a[i].id = i;
    sort(a + 1, a + 1 + n, [&](const node a, const node b) { return a.se < b.se; });
    int l = 1, r = n, m;
    while(l < r) {
        m = l + r + 1 >> 1;
        if(chk(m)) l = m;
        else r = m - 1;
    }
    if(!chk(l, 1)) return puts("0\n0"), void();
    printf("%d\n%d\n", l, SZ(ans));
    for(int i : ans) printf("%d ", i);
    puts("");
}
signed main() {
    int _; scanf("%d", &_); for(int cas = 1; cas <= _; cas++) solve();
    return 0;
}

K. Classical Summation Problem

题意

\(n\le10^6\) 个点，选 \(k\le10^6\) 个可重点，对于所有 \(n^k\) 种方案求出每种方案的中位数的点的编号之和。

题解

有朴素的二重求和式：

\[ \sum_{i=0}^{n-1}\sum_{a=0}^{\lfloor\frac{k-1}{2}\rfloor}i^a(n-i)^{k-a}\binom{k}{a} \]

然后你可以通过把 \(\binom{k}{a}\) 展开来得到一个可以用egf卷积的式子，然后你就 T 飞了。

正解是考虑中位数的期望，如果我们能求出期望，则答案就是 \(E\cdot n^k\) 。

当 \(2\nmid k\) 时，由于对称中位数期望显然是 \(\frac{n+1}{2}\) ，trival。

当 \(2\mid k\) 时，有一个很巧妙的办法是期望实际上为：

\[ E=\frac{n+1}{2}-\frac{1}{2}E'(\text{distance between two medians}) \]

考虑如何求出 \(E'\) ，有两种方法，一种是求长度为 \(l\) 的概率后求和，一种是对每一段 \([i,i+1]\) 算贡献，后者更加方便，则有：

\[ P(a_{k/2}\le i\land a_{k/2-1}>i)=P(i)=\binom{k}{k/2}i^k(n-i)^k \]

那么 \(E'=\sum\limits_{i=1}^{n-1}P(i)\) ，可以直接求得。

Code

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
const int P = 998244353;
int n, k;
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return res;
}
signed main() {
    scanf("%d %d", &n, &k);
    if(k % 2) return printf("%d\n", 1ll * (n + 1) * qpow(2, P - 2) % P * qpow(n, k) % P), 0;
    int binom = 1, iv = 1;
    for(int i = 1; i <= k; i++) binom = 1ll * binom * i % P;
    for(int i = 1; i <= k / 2; i++) iv = 1ll * iv * i % P;
    iv = qpow(iv, P - 2), binom = 1ll * binom * iv % P * iv % P;
    int E = 0;
    for(int i = 1; i < n; i++) {
        E = (E + 1ll * qpow(i, k / 2) * qpow(n - i, k / 2)) % P;
    }
    E = 1ll * E * binom % P;
    printf("%d\n", ((n + 1ll) * qpow(n, k) - E + P) % P * qpow(2, P - 2) % P);
    return 0;
}