11.17 模拟赛

禁止以一切形式传播或转载

T1:

给出 \(n,a,c\),求 \(\sum_{i=0}^n\left\lfloor\frac{a\times i}{c}\right\rfloor\),保证 \(c\mid n\)。结果对 \(998244353\) 取模。

\(n,a,c\le10^9\).

解:

\[\begin{aligned} \sum_{i=0}^n\left\lfloor\frac{a\times i}{c}\right\rfloor&=\sum_{i=0}^n \left(\frac{a\times n}{c}-\left\lceil\frac{a\times(n-i)}{c}\right\rceil\right)\\ &=\sum_{i=0}^n \left(\frac{a\times n}{c}-\left\lceil\frac{a\times i}{c}\right\rceil\right)\\ &=\sum_{i=0}^n\left(\frac{a\times n}{c}-\left(\left\lfloor\frac{a\times i}{c}\right\rfloor+1-\left[c\mid(a\times i)\right]\right)\right)\\ &=\left(n+1\right)\left(\frac{a\times n}{c}-1\right)+\sum_{i=0}^n\left[c\mid(a\times i)\right]-\sum_{i=0}^n\left\lfloor\frac{a\times i}{c}\right\rfloor\\ &=\left(n+1\right)\left(\frac{a\times n}{c}-1\right)+\frac{n\times\gcd(a,c)}{c}+1-\sum_{i=0}^n\left\lfloor\frac{a\times i}{c}\right\rfloor\\ \sum_{i=0}^n\left\lfloor\frac{a\times i}{c}\right\rfloor&=\frac{n\times\left(a\times\left(n+1\right)-c+\gcd(a,c)\right)}{2\times c} \end{aligned} \]


T2:

长度为 \(n\) 的数列,求其 \(k\) 阶前缀和 \(S_i^{(k)}\),答案对 \(998244353\) 取模。

\(n\le10^5,k\le2^{60}\).

解:

约定:

\[\large \begin{aligned} F_k(x)&=\sum_{i=0}^{n-1}S_{i+1}^{(k)}x^i\\ G(x)&=\sum_{i=0}^{n-1}x^i \end{aligned} \]

展开相乘,明显可知在 \(mod\ x^n\) 意义下:

\[\large \begin{aligned} \because S_i^{(k+1)}&=\sum_{j=1}^iS_j^{(k)}\\ \therefore F_k(x)\times G(x)&=\sum_{i=0}^{n-1}S_{i+1}^{(k)}x^i\sum_{j=0}^{n-1}x^j\\ &=\sum_{j=0}^{n-1}\sum_{i=0}^{n-1}S_{i+1}^{(k)}x^{i+j}\\ &\equiv\sum_{j=0}^{n-1}\sum_{i=0}^{n-j-1}S_{i+1}^{(k)}x^{i+j}\\ &\equiv\sum_{j=0}^{n-1}S_{n-j}^{(k+1)}x^{n-j-1}\\ &\equiv\sum_{j=0}^{n-1}S_{j+1}^{(k+1)}x^j\\ &\equiv F_{k+1}(x)\ (mod\ x^n) \end{aligned} \]

故所求 \(S_i^{(k)}\) 即 \((F_0(x)\times(G(x))^k)[i-1]\),\(F_0(x)\) 为 \(0\) 阶前缀和(原数列)的生成函数 \(\sum_{i=0}^{n-1}a_{i+1}x^i\)。

考虑 \((G(x))^k[i]\) 的意义:有 \(k\) 个数,每个数在 \([0,k-1]\) 之间,每个数的和为 \(i\) 的方案数。因为 \(i\le k-1\),所以不用担心上界问题,就相当于 \(k\) 个自然数的和为 \(i\) 的方案数。

众所周知方案数可以用插板法求出:\(i+k-1\) 个位置选出 \(k-1\) 个作为板,每相邻板之间的距离为一个数的大小。即:\(C_{i+k-1}^{k-1}\)。直接递推就行。

最后用 \(\text{NTT}\) 求 \(F_0(x)\) 和 \((G(x))^k\) 的卷积。

时间复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>

#define N 800000
#define mod 998244353
#define int long long

using namespace std;

template <typename T>
inline void read (T &a) {
	T x = 0, f = 1;
	char ch = getchar ();
	while (! isdigit (ch)) {
		(ch == '-') and (f = 0);
		ch = getchar ();
	}
	while (isdigit (ch)) {
		x = (x << 1) + (x << 3) + (ch xor '0');
		ch = getchar ();
	}
	a = f ? x : -x;
}
template <typename T, typename ...A>
inline void read (T &t, A &...a) {
	read (t), read (a...);
}
template <typename T>
inline void print (T x) {
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) print (x / 10);
	putchar (x % 10 + '0');
}

inline int qpow (int a, int b) {
	int res = 1;
	while (b) {
		(b bitand 1) and (res = res * a % mod);
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int a[N], b[N], n, k, len;

inline void NTT (int *a, int n, int f) {
	for (int i = k = 0; i < n; i++) {
		if (i > k) swap (a[i], a[k]);
		for (int j = n >> 1; (k xor_eq j) < j; j >>= 1);
	}
	for (int k = 2; k <= n; k <<= 1) {
		int tmp = qpow (3, (mod - 1) / k * f);
		for (int i = 0; i < n; i += k) {
			int w = 1, t;
			for (int j = i; j < i + (k >> 1); j++, w = w * tmp % mod) {
				t = w * a[j + (k >> 1)] % mod;
				a[j + (k >> 1)] = (a[j] - t + mod) % mod;
				a[j] = (a[j] + t) % mod;
			}
		}
	}
}

signed main () {
	freopen ("b.in", "r", stdin);
	freopen ("b.out", "w", stdout);
	read (n, k), b[0] = len = 1, k %= mod;
	for (int i = 0; i < n; i++) read (a[i]);
	for (int i = 1; i < n; i++) {
		b[i] = b[i - 1] * (k + i - 1) % mod * qpow (i, mod - 2) % mod;
	}
	while (len < (n << 1)) len <<= 1;
	NTT (a, len, 1);
	NTT (b, len, 1);
	for (int i = 0; i < len; i++) a[i] = a[i] * b[i] % mod;
	NTT (a, len, mod - 2);
	for (int i = 0; i < n; i++) {
		print (a[i] * qpow (len, mod - 2) % mod);
		puts ("");
	}
}

T3:

给出 \(n\) 个数 \(a_1,a_2,\cdots,a_n\),求出一个排列, 满足前 \(i\in[1,n]\) 个数的中位数单调不下降,输出字典序最大的排列。

解:

将 \(a\) 从小到大排序:

若 \(a_{\left\lceil\frac{n}{2}\right\rceil}=a_{\left\lceil\frac{n}{2}\right\rceil+1}\),则在构造过程中,可以让任意时刻的中位数等于 \(a_{\left\lceil\frac{n}{2}\right\rceil}\),维护两个堆 \(a\) 和 \(b\),分别存大于和小于 \(a_{\left\lceil\frac{n}{2}\right\rceil}\) 的数,构造时,先弹出 \(a_{\left\lceil\frac{n}{2}\right\rceil}\) 和 \(a_{\left\lceil\frac{n}{2}\right\rceil+1}\),之后再从 \(a\) 中弹出最大的,再从 \(b\) 中弹出最大的,以此类推。

如果存在 \(k<\left\lceil\frac{n}{2}\right\rceil\) 且 \(a_k=a_{k+1}\),与上类似。

否则选第一个数。

中位数显然要用对顶堆啊

#include <bits/stdc++.h>

#define N 100010

using namespace std;

template <typename T>
inline void read (T &a) {
	T x = 0, f = 1;
	char ch = getchar ();
	while (! isdigit (ch)) {
		(ch == '-') and (f = 0);
		ch = getchar ();
	}
	while (isdigit (ch)) {
		x = (x << 1) + (x << 3) + (ch xor '0');
		ch = getchar ();
	}
	a = f ? x : -x;
}
template <typename T, typename ...A>
inline void read (T &t, A &...a) {
	read (t), read (a...);
}
template <typename T>
inline void print (T x) {
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) print (x / 10);
	putchar (x % 10 + '0');
}

multiset <int> s;
priority_queue <int> A, B;
int a[N], v[N], n, p, q, mid;

inline void push (int x) {
	if (A.empty () or x <= A.top ()) A.push (x);
	else B.push (-x);
	if (A.size () < B.size ()) A.push (-B.top ()), B.pop ();
	if (A.size () > B.size () + 1) B.push (-A.top ()), A.pop ();
}

signed main () {
	freopen ("c.in", "r", stdin);
	freopen ("c.out", "w", stdout);
	read (n);
	for (int i = 1; i <= n; i++) read (a[i]);
	sort (a + 1, a + n + 1);
	mid = n + 1 >> 1;
	if (a[mid] == a[mid + 1]) {
		while (mid < n and a[mid] == a[mid + 1]) mid++;
		print (a[mid]);
		p = mid - 1, q = n;
		while (p or q > mid) {
			if (p) printf (" "), print (a[p--]);
			if (q > mid) printf (" "), print (a[q--]);
		}
		return 0;
	}
	while (mid > 1 and a[mid] != a[mid - 1]) mid--;
	print (a[mid]);
	v[mid] = 1;
	p = mid - 1, q = n;
	while (p and q > mid) {
		printf (" "), print (a[p]);
		v[p--] = 1;
		printf (" "), print (a[q]);
		v[q--] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (v[i]) push (a[i]);
		else s.insert (a[i]);
	}
	while (s.size ()) {
		p = *s.begin ();
		if (A.size () == B.size ()) {
			if (p >= -B.top ()) q = *--s.end ();
			else q = *s.begin ();
		} else {
			if(B.size () and p * 2 >= A.top () - B.top ()) q = *--s.end ();
            else q = *--s.upper_bound (p * 2 - A.top ());
		}
		printf (" "), print (q);
		s.erase (s.find (q)), push (q);
	}
}
上一篇:LeetCode-每日一题 397. 整数替换 [Java实现] [极速]


下一篇:模拟赛散题乱写