T4 标记

solution

  • 首先如果 gcd⁡(n,d)=1\gcd(n , d) = 1:

即 n,dn , d 互质的情况，那么将不会用重复标记的情况，此时 xx 将每次 +dmod  n+d\mod n 一直重复，答案为 (k×d)mod  n(k \times d) \mod n

  • 若 gcd⁡(n,d)≠1\gcd(n , d) \neq 1:

则当 xx 累加到 lcm(n,d)lcm(n , d) 时 xx 将取模到 00 由于 00 被标记过了，所以 xx 此时要额外加 11。易知，xx 一共要加 k×gcd⁡(n,d)n{k \times \gcd(n , d) \above 1pt n} 次，所以将产生的偏移量累加统计即可

code

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

int t , n , d , k;

int gcd(int a , int b){
	if(b == 0) return a;
	return gcd(b , a % b);
}

signed main(){
	freopen("D.in" , "r" , stdin);
	freopen("D.out" , "w" , stdout);
	
	cin >> t;
	
	while(t --){
		cin >> n >> d >> k;
		
		if(k == 1){
			cout << 0 << endl;
			continue;
		}
		k -= 1;
		cout << (k * d + k / (n / gcd(n , d))) % n << endl;
	}
	return 0;
}

T5 构成回文

solution

翻译下题目：要求求 A 的所有子数组都变为回文子数组所需要改变的元素的最小数量。

首先假设数组的元素全部不同，对于长度为 ll 的子数组，要改变 ⌊l2⌋\lfloor \frac l2 \rfloor 个元素才能变为回文子数组，所以对于所有的子数组，一共要改变的元素数量为：

$$cnt = \sum_{i = 2}^n{\lfloor \frac i2 \rfloor} \times (n - i + 1)$$

随后要减去相同元素所产生的贡献，因为若一对相同元素为 [pi,pj][p_i,p_j] 则所有以 pi,pjp_i,p_j 的中点为中心，包含 [pi,pj][p_i,p_j] 的子数组改变的元素数量都要减一，形式化地，产生贡献为：

k=min⁡(pi,n−pj+1)k = \min(p_i , n - p_j + 1)

直接用桶记录相同元素枚举显然会 T ，考虑优化暴力，可以用二分找到当前第一个 px≥n−pi+1p_x \geq n - p_i + 1 的位置，有：

  1. 在 xx 之前位置产生贡献为:
∑j<xpj\sum_{j < x}{p_j}
  1. 在 xx 之后位置产生贡献为：
(num−x+1)×(n−pi+1)(num - x + 1) \times (n - p_i + 1)

把两端的和加起来即可， xx 之前位置产生贡献可以用前缀和来处理

code

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

const int N = 2e5 + 5;

int n , a[N] , sum;
vector<int> g[N] , s[N];

int bs(int x , int h){
	int l = 1 , r = g[h].size() - 1;
	
	if(g[h][r] <= x) return r + 1;
	
	while(l < r){
		int mid = (l + r) >> 1;
		if(g[h][mid] - 1 >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

signed main(){
	freopen("E.in" , "r" , stdin);
	freopen("E.out" , "w" , stdout);
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int i = 2 ; i <= n ; i ++){
		sum += (i / 2) * (n - i + 1);
	}
	for(int i = 1 ; i <= n ; i ++){
		g[i].push_back(0) , s[i].push_back(0);
	}
	
	for(int i = 1 ; i <= n ; i ++){
		int num = g[a[i]].size();
		int x = bs(n - i , a[i]);
		if(num > 1) sum -= (num - 1) + (num - x) * (n - i) + s[a[i]][x - 1];
		
		g[a[i]].push_back(i);
		s[a[i]].push_back(s[a[i]][num - 1] + i - 1);
	}
	cout << sum;
	return 0;
}

T6 最大直径

solution

首先翻译下题面，找出所有长度为 nn 的序列 X：满足存在一颗树，使得树的每个顶点 ii 度数为 xix_i，同时最大化树的直径。求出所有长度为 nn 的序列 X 的树的直径之和

首先，容易发现一个性质：

∑i=1nxi=2n−2\sum_{i = 1}^n{x_i} = 2n - 2

即节点的度数之和为 22 倍的边数

其次，xi≥1x_i \geq 1，根据这两个性质可以推导出对于序列 X，其形成的好树直径最大为：

d=∑i=1n[xi>1]+1d = \sum_{i = 1}^n{[x_i > 1]} + 1

其中[]运算符 []内为真结果是 11，否则为 00

解释下这个式子，我们可以让所有的度数大于 1 的节点构成一条链，然后叶节点就挂在链上即可，链的直径显然为链上的节点数加 11

有了这个结论后就可以枚举叶节点的个数，显然叶节点的个数不同树的最大直径也就不同，设叶节点的个数为 kk , 则直径为 (n−k+1)(n - k + 1)。那么我们现在的问题就是求出叶节点个数为 kk 时所有序列 X 的个数

因为叶节点个数为 kk , 占用了 kk 个度数，其他节点的个数为 n−kn - k，占用了 2n−2−k2n - 2 - k 个度数，于是问题等价为有 2n−2−k2n - 2 - k 个球放在 n−kn - k 个箱子中的方案数，因为一个箱子内不能只放一个球，所以我们在所有箱子中放一个球，由隔板法知总方案有：

$$\begin{split} cnt &= \binom {2n - 2 - k - (n - k) - 1} {n - k - 1}\\ &=\binom {n - 3} {n - k - 1}\end{split}$$

由于叶节点有 kk 个，所以一共有 (nk)\binom nk 种选择叶节点的方案，根据乘法原理，再考虑上直径有：

$$ans = \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n-k+1)$$

显然，直接处理是 O(n)O(n) 的，会超时，所以到了我们愉快（痛苦）的推柿子时间啦！

在推式子之前，需要两个前置等式：

  1. 吸收恒等式:
k(nk)=n(n−1k−1)k\binom nk = n\binom{n - 1}{k - 1}

证明如下：

$$\begin{split} k\binom nk &= k {n! \above 1pt(n - k)!k!}\\ &= {n! \above 1pt(n - k)!(k - 1)!} \end{split}$$$$\begin{split} n\binom{n - 1}{k - 1} &= n {(n - 1)! \above 1pt(n - k)!(k - 1)!}\\ &= {n! \above 1pt(n - k)!(k - 1)!} \end{split}$$

的证

  1. 范德蒙德卷积:
$$\sum_{i = 0}^k{\binom ni \binom m{k - i}} = \binom {n + m}k$$

证明如下：

考虑原式的实际含义，在 n+mn + m 个数中选 kk 个显然等于在 nn 个数中选 ii 个再到 mm 个数中选 k−ik - i 个，再根据加法原理，将结果组合起来即可

推式子时间！（虽然看上去比较复杂，但实际还是不难的 awa）

$$\begin{split} ans &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n-k+1) \\ &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n - k - 1 + 2) \\ &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n - k - 1) + 2\sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1} \\ &= \sum_{k = 1}^n \binom nk \binom {n - 4} {n - k - 2}(n - 3) + 2\sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1} \\ &= \sum_{k = 1}^n \binom n{n - k} \binom {n - 4} {n - k - 2}(n - 3) + 2\sum_{k = 1}^n \binom n{n - k} \binom {n - 3} {n - k - 1} \\ &= (n - 3)\binom{2n - 4}{n - 2} + 2 \binom {2n-3}{n-1} \end{split}$$

可见我们已经推到为了组合数的形式，所以可以先预处理出组合数，再直接算即可，注意大数除法要用乘法逆元处理

时间复杂度：O(T+n)O(T + n)

code

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

const int N = 2e6 + 5;
const int mod = 998244353;

int t , n;
int inv[N + 5] , mul[N + 5];

int kmi(int a , int b){
	int res = 1;
	
	while(b){
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b /= 2;
	}
	return res % mod;
}

int C(int n , int m){
	if(n < m || n < 0 || m < 0) return 0;                                      // c_n^m
	return mul[n] * (inv[n - m] * inv[m] % mod) % mod;
}

signed main(){
	freopen("F.in" , "r" , stdin);
	freopen("F.out" , "w" , stdout);
	
	cin >> t;
	
	mul[0] = 1;
	for(int i = 1 ; i < N ; i ++){
		mul[i] = (i * mul[i - 1]) % mod;
	}
	inv[N - 1] = kmi(mul[N - 1] , mod - 2);
	for(int i = N - 1 ; i >= 0 ; i --){
		inv[i - 1] = (inv[i] * i) % mod;
	}
	
	while(t --){
		cin >> n;
		
		int tmp1 = ((n - 3) * C(2 * n - 4 , n - 2) % mod) % mod;
		int tmp2 = (2 * C(2 * n - 3 , n - 1) % mod) % mod;
		cout << (tmp1 + tmp2) % mod << endl;
	}
	return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.0-beta.13 Community