RT，挑了一些近期我打的模拟赛里的好题分享一下。
难度：CSP-S（少许题目超纲）
会持续更新。
题目 1
> 定义tree(x)\text{tree}(x)tree(x) 是 x−fibx-\text{fib}x−fib 树：
>
> * 若 x=0x=0x=0，则为空树；
> * 若 x=1x=1x=1，则为只有一个节点的树；
> * 若 x>1x>1x>1，则为一个节点下连接两个儿子：左儿子是 tree(x−1)\text{tree}(x-1)tree(x−1)，右儿子是 tree(x−2)\text{tree}(x-2)tree(x−2)。
>
> 现在 A 和 B 在玩游戏，A 先手。每个人可以选择一个子树删除，删掉根节点的人输。
>
> 求 tree(n)\text{tree}(n)tree(n) 里有多少个 A 的必胜点。
>
> 1≤n≤1041\leq n\leq 10^41≤n≤104。
我们先考虑建出整棵树之后怎么做。删子树不好考虑，改成删子树根节点连向父亲的边，无法操作者输。考虑 SG 函数，令 sg(u)sg(u)sg(u) 表示将以 uuu 为根节点的子树中的边全部删除的 SG 值。
如果 uuu 是叶子，则 sg(u)=0sg(u)=0sg(u)=0，代表这个点先手必输。
如果 uuu 有且只有一个儿子 vvv，则有 sg(u)=sg(v)+1sg(u)=sg(v)+1sg(u)=sg(v)+1。按照定义，这相当于在 vvv 这 sg(v)sg(v)sg(v) 个石子上增加了一个石子 v→uv\rightarrow uv→u。
如果 uuu 有多个儿子，按照定理，sg(u)=⨁v∈son(u)(sg(v)+1)sg(u)=\bigoplus_{v \in \operatorname{son}(u)} (sg(v)+1)sg(u)=⨁v∈son(u) (sg(v)+1)。其中 +1+1+1 是 v→uv\rightarrow uv→u 的边。
这可能不太容易理解，画个图：
这样我们只能通过 sg(1)sg(1)sg(1) 求出开始是否必胜，所以我们还得枚举第一步的决策，判断删除第一步的子树后对手是否必败。时间复杂度 O(m2)O(m^2)O(m2)，其中 mmm 是树的点数。大概是 1.618n1.618^n1.618n 的级别。
发现题目给出的树比较特殊，或许可以利用斐波那契的性质递推一下。设 fi,jf_{i,j}fi,j 表示在 tree(i)\operatorname{tree}(i)tree(i) 中，删除一个子树（不是根）使得 sg(1)=jsg(1)=jsg(1)=j 的方案数。我们需要求 fn,0f_{n,0}fn,0 。
为了转移，我们还需要设一个 gig_{i}gi 表示 tree(i)\operatorname{tree}(i)tree(i) 中的 sg(1)sg(1)sg(1)。
那么有转移：
fi,j=fi−1,j⊕(gi−2+1)−1+fi−2,j⊕(gi−1+1)−1gi=(gi−1+1)⊕(gi−2+1)f_{i,j}=f_{i-1,j\oplus (g_{i-2}+1)-1}+f_{i-2,j\oplus (g_{i-1}+1)-1} \\ g_{i}=(g_{i-1}+1)\oplus (g_{i-2}+1) fi,j =fi−1,j⊕(gi−2 +1)−1 +fi−2,j⊕(gi−1 +1)−1 gi =(gi−1 +1)⊕(gi−2 +1)
我们会发现 fff 的转移过程中下标可能变成负数，这意味着，在 sg(1)=jsg(1)=jsg(1)=j 的情况下，这个儿子不存在，也就是说我们把 iii 与这个儿子间的边删除了。所以遇到非法情况，我们需要让 fi,j←fi,j+1f_{i,j}\gets f_{i,j}+1fi,j ←fi,j +1。
根据 sgsgsg 的边界，有 f,gf,gf,g 的边界：
f2,0=1g1=0g2=1f_{2,0}=1 \\ g_1=0 \\ g_2=1 f2,0 =1g1 =0g2 =1
发现 sg(n)=O(n)sg(n)=O(n)sg(n)=O(n)，时间复杂度 O(n2)O(n^2)O(n2)。
难度：紫。
Code:
题目 2
> 给定一个 n×mn\times mn×m 的 010101 矩阵，设两点的距离为它们的欧几里得距离的平方。你需要对于每一个点 (x,y)(x,y)(x,y)，求出上、下、左、右（允许同行同列）的 111 点中离它最近的那个的距离。不存在则定义为 10910^9109。
>
> 输出量较大，设 (x,y)(x,y)(x,y) 上方的最近 111 点距离为 upx,yup_{x,y}upx,y ，求 ⨁x,yupx,y\bigoplus_{x,y} up_{x,y}⨁x,y upx,y 。另外三个同理。
>
> 1≤n,m≤40001\leq n,m\leq 40001≤n,m≤4000。
O(n4)O(n^4)O(n4) 毫无意义，直接来考虑三次方做法。
四个方向本质相同，我们只讨论 upupup。设 sjs_jsj 表示第 jjj 列上，最靠下的 111 点的位置。我们按照 i=1,2,…,ni=1,2,\dots,ni=1,2,…,n 的顺序处理每一行，若 ai,j=1a_{i,j}=1ai,j =1，则更新 sj←1s_j\gets 1sj ←1。那么 (i,j)(i,j)(i,j) 的答案即为 mink=1m((i−sk)2+(j−k)2)\min_{k=1}^m ((i-s_k)^2+(j-k)^2)mink=1m ((i−sk )2+(j−k)2)。时间复杂度 O(n3)O(n^3)O(n3)。
考虑推一下式子：
upi,j=min((i−sk)2+(j−k)2)=min((i−sk)2+j2−2kj+k2)=j2+min(−2kj+k2+(i−sk)2)up_{i,j}=\min((i-s_k)^2+(j-k)^2)=\min((i-s_k)^2+j^2-2kj+k^2)=j^2+\min(-2kj+k^2+(i-s_k)^2) upi,j =min((i−sk )2+(j−k)2)=min((i−sk )2+j2−2kj+k2)=j2+min(−2kj+k2+(i−sk )2)
设 jjj 是自变量，则要求的式子形如 min(kx+b)\min(kx+b)min(kx+b)，斜率优化。发现斜率是 −2k-2k−2k，单调递减；查询的是 j=1,2,…,mj=1,2,\dots,mj=1,2,…,m，单调递增；所以可以单调队列维护下凸包。时间复杂度 O(nm)O(nm)O(nm)。
难度：蓝。
Code:
题目 3
> 给定 nnn 个点 mmm 条边的带边权有向图，每个点有开放时间，若当前时间 TTT 满足：li≤T mod ti≤ril_i\leq T\bmod t_i\leq r_ili ≤Tmodti ≤ri ，则可以从此点出发到其它点。你有两种状态：停止状态和移动状态，初始你是停止状态。如果你处于停止状态的时候想移动，必须额外消耗 kkk 时间变成移动状态。移动之后如果你能不停歇地继续移动，则可以不切换为停止状态。
>
> 注意，如果在时间 TTT，点 iii 开启了，并且你处于停止状态，那么无论 T+kT+kT+k 时间时点 iii 是否开启，你都可以通过。也就是说，能否通过一个点取决于你准备移动地那一刻。
>
> 求 111 到所有点的最短路。
>
> 2≤n,m≤5×1032\leq n,m\leq 5\times 10^32≤n,m≤5×103，0≤k≤1030\leq k\leq 10^30≤k≤103，1≤w≤1031\leq w\leq 10^31≤w≤103，2≤ti≤102\leq t_i\leq 102≤ti ≤10，0≤li≤ri<ti0\leq l_i\leq r_i<t_i0≤li ≤ri <ti ，没有重边自环。
首先经过 LCM(t)\operatorname{LCM}(t)LCM(t) 的时间，所有点的开放状态会回归初始，而 ttt 很小，可以计算出这个循环时间为 252025202520。
建立分层图，设 distu,T,0/1dist_{u,T,0/1}distu,T,0/1 表示到达点 uuu，此时时间为 TTT（满足 0≤T<25200\leq T<25200≤T<2520），状态为停止还是移动的最短路。朴素实现复杂度大概是 O(mTlogmT)O(mT\log mT)O(mTlogmT)。不可通过。
发现 k,wk,wk,w 也很小，且 k+w<2520k+w<2520k+w<2520，说明经过一条边之后，循环次数只会 +0+0+0 或 +1+1+1。这令我们想到 01bfs。设 distu,T,0/1dist_{u,T,0/1}distu,T,0/1 表示最小经过循环次数，使用 01bfs 跑即可。答案为 mini(2520×min(distu,i,0,distu,i,1)+i)\min_i(2520\times \min(dist_{u,i,0},dist_{u,i,1})+i)mini (2520×min(distu,i,0 ,distu,i,1 )+i)。
时间复杂度：O(mT)O(mT)O(mT)。
难度：青。
Code:
题目 4
> 给定 nnn 个居民，编号 1,2,…,n1,2,\dots,n1,2,…,n，再给定 nnn 个礼物，编号 m+1,m+2,…,m+nm+1,m+2,\dots,m+nm+1,m+2,…,m+n。居民 iii 只喜欢要 iii 的倍数的礼物。求有几种分配方案使得每个人都恰好有 111 个礼物。
>
> 1≤n≤1091\leq n\leq 10^91≤n≤109，1≤m≤201\leq m\leq 201≤m≤20。
假设 n≤mn\leq mn≤m，状压就行。我们只考虑 n>mn>mn>m 的做法。
假设居民 iii 拿到了 jjj。如果 i=ji=ji=j，那么无事发生；如果 i<ji<ji<j，那么我们接着考虑 jjj 怎么办。jjj 肯定还得拿一个 kkk，kkk 也得接着拿，以此类推，最终拿到哪里呢？拿到一个 >n>n>n 的数截止。
我们发现 [m+1,n][m+1,n][m+1,n] 里面的居民可以无事发生，所以先不管；但是 [1,m][1,m][1,m] 的居民只能拿其他人的。对于 1≤i≤m1\leq i\leq m1≤i≤m，假设他拿了 a1a_1a1 ，则有 i∣a1i\mid a_1i∣a1 ；接着，有 a1∣a2a_1\mid a_2a1 ∣a2 。因此，设最后 j>nj>nj>n，有 i∣a1∣a2∣⋯∣ji\mid a_1\mid a_2\mid \dots\mid ji∣a1 ∣a2 ∣⋯∣j。我们思考这个的方案数怎么求。
设这个倍数的过程，每次乘上了 ttt，则有：
j=it1t2…tK∏t=jij=it_1t_2\dots t_K\\ \prod t=\frac{j}{i} j=it1 t2 …tK ∏t=ij
同时满足 tk>1t_k>1tk >1。
我们来求这个的方案数，直接枚举因数再记忆化搜索就可以，时间复杂度 O(玄学)O(玄学)O(玄学)。设分解 x=jix=\frac{j}{i}x=ij 的方案数为 F(x)F(x)F(x)。
此时可能会有一个问题，就是两条不同的倍数链会不会相交在某一个点？假设这个点是 ttt，显然：
{m+1≤t≤nt∣j1t∣j2∴t∣(j1−j2)∵j1−j2<m∴t<m\begin{cases} m+1\leq t\leq n\\ t\mid j_1\\ t\mid j_2\\ \end{cases}\\ \therefore t\mid (j_1-j_2)\\ \because j_1-j_2<m\\ \therefore t<m ⎩⎨⎧ m+1≤t≤nt∣j1 t∣j2 ∴t∣(j1 −j2 )∵j1 −j2 <m∴t<m
所以不会相交。
然后我们发现，这个链的第一个数是 [1,m][1,m][1,m]，但是第二个数应该是 [m+1,n][m+1,n][m+1,n] 的，所以还需要特意枚举一下每条链的第二个数。应该有 t1>mit_1>\frac{m}{i}t1 >im 。
那么，我们设 f(i,j)f(i,j)f(i,j) 表示，当第一个数是 iii，最后一个是 jjj 的时候的方案数，容易得到：
f(i,j)=F(ji)−∑2≤k≤mi,k∣jiF(jik)f(i,j)=F(\frac{j}{i})-\sum_{2\leq k\leq \frac{m}{i},k\mid \frac{j}{i}} F(\frac{\frac{j}{i}}{k}) f(i,j)=F(ij )−2≤k≤im ,k∣ij ∑ F(kij )
时间复杂度是 O(m2logm⋅玄学)O(m^2\log m\cdot 玄学)O(m2logm⋅玄学)
然后我们就可以考虑状压求解总方案了。设 dpsdp_{s}dps 表示，将 [1,popcount(s)][1,\operatorname{popcount}(s)][1,popcount(s)] 的数作为起点，n+{s}n+\{s\}n+{s} 集合作为终点的分配方案数。有 dp0=1dp_{0}=1dp0 =1。
然后我们考虑转移进来下一个终点 iii。设 t=popcount(s)t=\operatorname{popcount}(s)t=popcount(s)，有：
dps∣2i←dps,if(t+1,n+i)dp_{s|2^i}\gets dp_{s,i}f(t+1,n+i) dps∣2i ←dps,i f(t+1,n+i)
时间复杂度：O(2mm+m2logm⋅玄学)=O(能过)O(2^mm+m^2\log{m}\cdot 玄学)=O(能过)O(2mm+m2logm⋅玄学)=O(能过)。
难度：紫。
Code:
