闲话8.23

护照在第\(i\)个点买一张票，就能在\([L_i,R_i]\)中任意行走，求从每个点出发，最少买几张票能走遍\([1,n]\)？tag：最短路，线段树优化建图。题目的问题是求最少代价，于是我们发现题目很像一个最短路模型：\(i\)向一个虚点\(u_i\)连边权为\(1\)的边，\(u_i\)向\([L_i,R_i]\)连代......

A一条蛇，有\(K(K\le6)\)个格子，格子必须连续且不能重叠。在\(n\timesm(n,m\le3000)\)的矩阵中放置，有一些格子是不能放的，问方案数。B一棵树\((n\le50000)\).每次询问\([l1,r1],[l2,r2]\)在\(rt\)为根下两两lca的异或和。先处理以\(rt\)为根的问题，发现\(lca_{......

闲话8.23起因是Rolling_star在考古IMO时发现了这样一道预选题：给出序列\(\{a_n\}\)满足：\[2^n=\sum_{d|n}{a_d}\]求证：\[n|a_n\]我们先做一遍底幂交换（\(Base\)\(power\)\(exchange\)）:\[2^d=\sum_{n|d}a_n\]然后再指数降阶（$Exponential$$reduction$）:\[\bm{2\tim......

T1先应该想到\(n^2\)做法，显然连线有交叉是不优的，所以连线不交叉。T2首先\(x^{p_i}\equivq_i(\operatorname{mod}n)\Rightarrowx^{p_i}\equivq_i(\operatorname{mod}p_i)\)然后根据费马小定理或者从\(x^{p_i-2}\equivx^{-1}(\operatorname{mod}p_i)\)可以推出\(x^{......

我觉得\(A\)和\(C\)还是能做一点的。就是考场上太劣了去找ABC写了。A在\(n\timesm\)的矩阵中放一条长为\(k\)的蛇，其中一些位置有限制。蛇有顺序之分，问总方案数。\(n,m\le3000\)，\(k\le6\).B给出一棵树，多次询问，给出\(root,l_1,r_1,l_2,r_2\)，问以\(root\)为根......

因为模拟赛太频繁已经很久没有写闲话了今天搜到的一道IMOShortlist题，挺水的，但是还挺好玩先反演一波：\[a_n=\sum_{d|n}2^d\mu(\fracnd)\]然后因为\(\mu\)和\(2^n\)都是积性的，所以\(a_n\)是积性的，只需要考虑素数幂处的取值即可\[a_{p^k}=\sum_{i=0}^{k}2^{p^i}\mu(......

今天接着摆！上午jimmy让vp场CF，结果A题5分钟切，B题调一个多小时没调出来......

今天真的摆了一天。上午jimmy让做一个S组模拟，当学考做的......

今天好像又摆了一天......

今天依旧睡到7点半......