qbxt D9 && NOIP提高组考前刷题冲刺班（第九场）

不用讲了

倍增DP是可以的!

可以组合计数!

不用讲了

容斥,注意乘上每个组内部排序(3!的次方)的方案数



//容斥
#include<bits/stdc++.h>
const int MAXN = 4e6 + 7;
#define ll long long
using namespace std;
const int P = 998244353;//摸错人
int n, N;
int fac[MAXN], ifac[MAXN];
ll cf6[MAXN];
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 add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline void sub(ll &x, ll y) {
	x -= y;
	if(x < 0)x += P;
}

inline void init() {
	fac[0] = 1;
	ifac[0] = 1;
	for(int i = 1; i <= N; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[N] = ksm(fac[N], P - 2);
	for(int i = N - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	cf6[0] = 1;
	for(int i = 1; i <= n; ++i)cf6[i] = cf6[i - 1] * 6 % P;
	return;
}

inline ll C(int n, int m) {
	return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

inline void solve() {
	ll ans = fac[N];
	for(int i = 1; i <= n; ++i) {
		if(i & 1)sub(ans, cf6[i] * C(n, i) % P * fac[N - 2 * i]  % P);
		else add(ans, cf6[i] * C(n, i) % P * fac[N - 2 * i]  % P);
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%d", &n);
	N = 3 * n;
	init();
	solve();
	return 0;
}

直接树套树剖竟然三个log过5e5

一个点在这个路径上,和其中某几个端点查LCA一定是这个路径本身,或者这个dis和等于两点距离

那么我们能 $n^2$ 预处理然后 $O(1)$ 查询!

OnO1rmq....其实写n^2暴力没有这么复杂吧.....

最小值可以二分一下?假设答案至少为x

相当于小于x的路径和节点都有交集

树链求交

四个端点两两LCA(一条路径上的除外)

然后LCA排序一下重复的和不在路径上的点去掉后选后两个

大概分类讨论一下

我们能维护这个交集

把链按照权值排序,求一个前缀交集和后缀交集

二分这个点的答案

大概可以 $O(nlogn)$

这样不带删除或者修改操作就解决了

$splay$
$CDQ$
$离线$

线段树分治吧?

就是考虑单点修改直接改,然后回溯回复整个序列

线段树直接做?

就是离线,把所有可能的边情况拿出来

然后排序,建立线段树,之后就是一个区间路径交的维护

然后我们就能做了?

卢卡斯

$C_{n,m}=C_{n/p,m/p}*C_{n%P,m%P}$

$C_{n,m}$ %P

模合数?

可以质因数分解为每个,然后再做下面的阶乘

$n!=p^aN$ ,然后觳觫的部分直接做(互素)

P=1e9+7

第k小子集和

$n<=30$

二分一下

然后mit in middle即可判断这个的rank

夏晓光(loveJY)的博客

qbxt D9 && NOIP提高组考前刷题冲刺班（第九场）

qbxtD8 && NOIP提高组考前刷题冲刺班（第八场）