NOI Online 提高组 Day2

比赛经历

按序开题，写了 T1 正解后写了 T270。然后使用了一些神秘力量学会了 T3（其实就是 xd 指点了一下）。

回来把 T2 卡卡常就卡进 2s 了。

涂色游戏

你有$10^{20}$个格子，它们从$0$开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：

1. 编号是$p_1$倍数的格子（包括$0$号格子，下同）染成红色。
2. 编号是$p_2$倍数的格子染成蓝色。
3. 编号既是$p_1$倍数又是$p_2$倍数的格子，你可以选择染成红色或者蓝色。

其中$p_1$和$p_2$是给定的整数，若格子编号是$p_1$或$p_2$的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在$k$个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定$p_1,p_2,k$，你想知道是否有一种染色方案不是无聊的。

$1\le T\le 10^6,1\le p_1,p_2,k\le 10^9$.

暴力

如果$p_1=p_2$就是 Yes。如果$k=1$就是 No。

否则不妨设$p_1>p_2$，首先可以除掉 gcd。然后答案是$[\lceil \frac{p_1-2}{p_2} \rceil<k]$。

代码

子序列问题

给出一个长度为$n$的正整数序列$a_1,\cdots,a_n$。定义$f(l,r)$表示区间$[l,r]$中不同数字的个数。

求$\sum_{1\le l\le r\le n}(f(l,r))^2$，对$10^9+7$取模。

线段树 扫描线 卡常

考虑扫描线，那么左端点移动的时候，会把一个区间的值减 1。

线段树维护区间加，求区间平方和即可。

时间复杂度$O(n\log_2n)$。

代码

游戏

有一棵$2m$个结点的有根树。其中有$m$个点是黑点，其他$m$个点是白点。现在你要把黑点白点两两匹配，一个匹配方案的权值是其中祖孙匹配的个数。

求权值为$0,1,\cdots,m$的匹配的个数。

两个匹配不同当且仅当存在一个黑点使得在两个方案中匹配的白点不同。

$m\le 2500$。

容斥 二项式反演 DP

设$f(i,j)$表示在$i$的子树中选$j$对祖孙匹配的方案数，其他点不匹配。

对于根结点的 DP 值，把其他点任意匹配的方案数乘上去（阶乘），然后二项式反演即可。

时间复杂度$O(m^2)$。

代码