NOIP提高组考前刷题冲刺班（第二场）

完蛋啦

异或是不进位加法,所以全分一段和全分是两种极端情况

考虑期望的线性性,相当于计算一个的期望

而会发现这个和抛硬币没什么区别

概率为1/p的期望为p

所以答案为 $ny/x$

f_n=1+pf_{n-1}+(1-p)f_{n}

也是可以发现f是等差数列

本人考场做法:

期望线性性后

考虑一个数第几次被选走

设p为取走的,q为没取走的概率

p+2pq+3pq^2+4pq^3....

等于

p(1+2q+3q^2+4q^3....)

而这个东西是等比乘等差求和的时候

突然好多标记

维护 $(x+a)/b+c$

然后会发现这个可以合并

\lfloor\frac{\lfloor\frac{x+a}{b}\rfloor+c+a'}{b'}\rfloor+c'

a_1=a+b*c+b*a'

b_1=b*b'

c_1=c'

然后你会发现 $a_1$ 可以对 $b_1$ 取模

$b_1$ 可以爆longlong!?

不过当 $b_1$ 特别大的时候是没有意义的

因为当 $b_1$ 达到inf(1e9)的时候除法相当于

$x>=b-a?1:0$

(x不可能达到1e9量级)

此时b,a同时减去超过 $1e9$ 的部分即可!

做法2

在每个节点上维护log个pair,表示 $+x/y$

显然发现我们下传标记是log清空,而多余log的标记没有意义


#include<bits/stdc++.h>
#define ll long  long
using namespace std;
const int MAXN = 1e6 + 7;
int n, m;
struct rec {
	ll a, b, c, lz, mx;
	rec(int A = 0, int B = 1, int C = 0, int LZ = 0, int MX = 0): a(A), b(B), c(C), lz(LZ), mx(MX) {};
	bool operator!=(const rec &x) const {
		return x.a != a || x.b != b || x.c != c;
	}
} tr[MAXN];
int a[MAXN], rc[MAXN];
const int inf = 1e9;
rec operator+(const rec &x, const rec &y) {
	rec nw = rec();
	nw.mx = x.mx;
	nw.lz = x.lz;
	nw.a = x.a + x.b * x.c + x.b * y.a;
	nw.b = x.b * y.b;
	nw.c = y.c;//order?
	nw.c += nw.a / nw.b;
	nw.a %= nw.b;
	if(nw.b > inf) {
		nw.a = max(0ll, nw.a - (nw.b - inf));
		nw.b = inf;
	}
	return nw;
}

inline void pushdown(int k) {
	// printf("pd : %d %d? %d %d %d %d??\n", k, tr[k].b, tr[k].a, tr[k].c, tr[k].mx, tr[k].lz);
	if(tr[k].lz) {
		tr[k << 1 | 1] = rec(0, 1, 0, 1, rc[k << 1 | 1]);
		tr[k << 1] = rec(0, 1, 0, 1, rc[k << 1]);
		tr[k].lz = 0;
	}
	if(tr[k] != rec()) {
		tr[k << 1 | 1] = tr[k << 1 | 1] + tr[k];
		// printf("pd 1 :%d %d\n", tr[k << 1].mx, tr[k << 1 | 1].mx);
		tr[k << 1] = tr[k << 1] + tr[k];
		tr[k << 1].mx = (tr[k << 1].mx + tr[k].a) / tr[k].b + tr[k].c;
		tr[k << 1 | 1].mx = (tr[k << 1 | 1].mx + tr[k].a) / tr[k].b + tr[k].c;
		// printf("pd 2 :%d %d %d %d %d\n", tr[k << 1].mx, tr[k << 1 | 1].mx, tr[k].b, tr[k].a, tr[k].c);
		tr[k] = rec(0, 1, 0, tr[k].lz, tr[k].mx);
	}
	return ;
}

inline void build(int k, int L, int R) {
	tr[k].b = 1;
	if(L == R) {
		tr[k].mx = a[L];
		rc[k] = tr[k].mx;
		return ;
	}
	int mid = (L + R) >> 1;
	build(k << 1, L, mid);
	build(k << 1 | 1, mid + 1, R);
	// printf("build :%d %d %d %d \n", L, R, tr[k << 1].mx, tr[k << 1 | 1].mx);
	tr[k].mx = max(tr[k << 1].mx, tr[k << 1 | 1].mx);
	// printf("b tr mx :%d \n", tr[k].mx);
	rc[k] = tr[k].mx;
}

inline void add(int k, int L, int R, int l, int r, int x) {
	// printf("ad :%d %d %d %d %d\n", k, L, R, x, tr[k].mx);
	if(l <= L && R <= r) {
		tr[k].mx += x;
		tr[k].c += x;//qaq
		return ;
	}
	pushdown(k);
	int mid = (L + R) >> 1;
	if(l <= mid)add(k << 1, L, mid, l, r, x);
	if(mid < r)add(k << 1 | 1, mid + 1, R, l, r, x);
	tr[k].mx = max(tr[k << 1].mx, tr[k << 1 | 1].mx);
}

inline void div(int k, int L, int R, int l, int r, int x) {
	// printf("div : %d %d %d %d %d %d ???a: %d b %d\n", k, L, R, l, r, tr[k].mx, tr[k].a, tr[k].b);
	if(l <= L && R <= r) {
		rec nw = rec(0, x, 0, 0, 0);
		tr[k] = tr[k] + nw;
		tr[k].mx /= x;
		return ;
	}
	pushdown(k);
	int mid = (L + R) >> 1;
	if(l <= mid)div(k << 1, L, mid, l, r, x);
	if(mid < r)div(k << 1 | 1, mid + 1, R, l, r, x);
	tr[k].mx = max(tr[k << 1].mx, tr[k << 1 | 1].mx);
}

inline void callback(int k, int L, int R, int l, int r) {
	if(l <= L && R <= r) {
		tr[k] = rec(0, 1, 0, 1, rc[k]);
		return ;
	}
	pushdown(k);
	int mid = (L + R) >> 1;
	if(l <= mid)callback(k << 1, L, mid, l, r);
	if(mid < r)callback(k << 1 | 1, mid + 1, R, l, r);
	tr[k].mx = max(tr[k << 1].mx, tr[k << 1 | 1].mx);
}

inline ll qry(int k, int L, int R, int l, int r) {
	// printf("qry : %d %d %d %d %d %d ???a: %d b %d\n", k, L, R, l, r, tr[k].mx, tr[k].a, tr[k].b);
	if(l <= L && R <= r) return tr[k].mx;
	pushdown(k);
	int mid = (L + R) >> 1;
	if(r <= mid)return qry(k << 1, L, mid, l, r);
	else if(l > mid)return qry(k << 1 | 1, mid + 1, R, l, r);
	else return max(qry(k << 1, L, mid, l, r), qry(k << 1 | 1, mid + 1, R, l, r));
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	build(1, 1, n);
	for(int i = 1, t, l, r, x; i <= m; ++i) {
		scanf("%d%d%d%d", &t, &l, &r, &x);
		++l;
		++r;
		if(t == 0) {
			add(1, 1, n, l, r, x);
		} else if(t == 1) {
			div(1, 1, n, l, r, x);
		} else if(t == 2) {
			printf("%lld\n", qry(1, 1, n, l, r));
		} else {
			callback(1, 1, n, l, r);
		}
	}
	return 0;
}

枚举最大值,然后会发现我们有相当多的数,他们有固定的一些对象选择配对(不能超过最大值)

比如2n+3,2n只能和1,2配对

然后我们就可以算出来,求一个次幂

剩下的数是两两匹配的方案数 $f_i=f_i-2*(i-1)$



//冲了,艹
//为什么他妈的他们能做老子不能
//冲了
//不就是枚举最大值然后考虑剩下的pair中那些能自由那些只有固定的方案吗
//然后强制让一个达到上界就行
#include<bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int MAXN = 5e5 + 7;
#define ll long long
int n;
ll fac[MAXN], ifac[MAXN];
ll f[MAXN];//i个人自由匹配方案数!!!
ll ans;
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

//自由...自由...种树啊!!!
inline void init() {
	fac[0] = 1;
	int N = 2 * n;
	for(int i = 1; i <= N; ++i) {
		fac[i] = fac[i - 1] * i % P;
	}
	ifac[N] = ksm(fac[N], P - 2);
	ifac[0] = ifac[1] = 1;
	for(int i = N - 1; i >= 2; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % P;
	}
	f[0] = 1;
	for(int i = 2; i <= N; i += 2) {
		f[i] = f[i - 2] * (i - 1) % P; //把i和i-1中某个人绑起来
	}
	//种种种...........
	return ;
}

int main() {
	// freopen("test.in", "w", stdout);
	scanf("%d", &n);
	int N = 2 * n;
	init();
	//如果不是偶数,那可坏透了
	for(int i = N + 2; i <= 2 * N - 1; i++) { //最小...最大....
		// if(i & 1) {//偶数,我们在i/2 + 1的时候停下
		// printf("!! : %d ", i);
		int y = N - (i / 2);//这些pair选好了!!!
		// printf("%d ", y);
		ll tmp = ksm(2, n) * fac[n] % P; //随便换
		// printf("%lld \n", tmp);
		tmp = tmp * f[N - y * 2] % P; //这些,自由了!!!!
		// printf("%lld \n", tmp);
		if(y > 1) {
			tmp = tmp * ksm(i - N - 1, y - 1) % P; //艹!!!
			// printf("%d %d %lld ???\n", y - 1, i - N - 1, tmp);
		}
		tmp = tmp * y % P; //还有一个!!我们要选择哪个自闭!!!
		// printf("%lld this is free!!\n", tmp);
		ans = (ans + tmp) % P;
		// } else {//坏透了!!!
		// 	int y = N - (i / 2);
		// }
	}
	printf("%lld\n", 1ll * ans * ksm(fac[N], P - 2) % P);
	return 0;
}

夏晓光(loveJY)的博客

NOIP提高组考前刷题冲刺班（第二场）

ARC杂题选讲P1