[Nescafé 18&COGS 1045] 七夕祭 题目解析

    注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题后受到伤害！！！）

  引入

       你有一个 \(N \times M\) 的矩形网格，其中 \(T\) 个格点是“感兴趣的”。你可以交换相邻的格点（左右相邻或上下相邻，且每行/列的首尾也算相邻，即环形）。目标是用最少的交换次数，同时满足两个条件：

1. 行均等：每一行感兴趣的格点数相同。

2. 列均等：每一列感兴趣的格点数相同。

这是一个典型的环形均分问题。核心思想是：行列独立，可以分别求解。

分析

第 1 步：数据统计与可行性预判

统计行和：设第 \(i\) 行有 \(R_i\) 个感兴趣的格点，则 \(\sum_{i=1}^{N} R_i = T\)。

统计列和：设第 \(j\) 列有 \(C_j\) 个感兴趣的格点，则 \(\sum_{j=1}^{M} C_j = T\)。

 预判可行性：

行方向可行的条件是 \(T\) 能被 \(N\) 整除。此时每行的目标数为 \(\text{avg}_R = \frac{T}{N}\)。

列方向可行的条件是 \(T\) 能被 \(M\) 整除。此时每列的目标数为 \(\text{avg}_C = \frac{T}{M}\)。

第 2 步：将行/列问题转化为一维环形均分问题

以行方向为例，我们得到了一个环形排列的数列 \([R_1, R_2, ..., R_N]\)，需要通过相邻交换（环形），使每个数都变成目标值 \(\text{avg}_R\)。这本质上是一个货物搬运问题。

转化：

我们定义一个“偏差”数组 \(A_i = R_i - \text{avg}_R\)。问题变成了：通过相邻搬运，使所有 \(A_i\) 变为 0。最终答案是所有搬运的“工作量”之和。

第 3 步：求解一维环形均分问题（数学推导）

设从第 \(i\) 个位置搬运到第 \(i+1\) 个位置的货物量为 \(x_i\)（可正可负，正表示向右搬，负表示向左搬）。那么，对于每个位置，经过搬运后，其偏差应该被消除：

\[

   A_i + x_{i-1} - x_i = 0

   \]

其中 \(x_0\) 表示从第 \(N\) 个位置到第 \(1\) 个位置的搬运量（因为是环形）。整理得：

\[

   x_i = A_i + x_{i-1}

   \]

这是一个递推关系。令 \(x_0 = k\)，则可以推出：

\(x_1 = A_1 + k\)

\(x_2 = A_2 + x_1 = A_1 + A_2 + k\)

\(x_3 = A_1 + A_2 + A_3 + k\)

...

 \(x_i = S_i + k\)

其中 \(S_i = \sum_{j=1}^{i} A_j

........................................................................

该题解待审

........................................................................(剩余 3569 个中英字符)

场上被这道题送走了。

直接做显然是很困难的，不过根据期望的性质，我们可以把答案的贡献拆到每一个子树上，具体的，对于一个大小为 $siz_x$ 的子树 $x$，若 $(x,fa_x)$ 成为重边的概率为 $P$，则这个子树对答案的贡献为 $(1-P)siz_x$。

接下来就是求出 $P=\frac{l_i}{\sum_{j=1}^k l_j}$ 了，显然我们可以在树上做 dp，并分别记录 $f_{i,j}$ 表示 $i$ 下有一条长度为 $j$ 重链的概率，$g_{i,j}$ 表示 $i$ 所有儿子重链长度之和为 $j$ 的概率。

$g_{i,j}$ 的转移是一个树上背包状物，不断让 $g,f$ 卷积即可，根据经典结论，树上背包的时间复杂度由每个点对贡献得来，复杂度为 $O(n^2)$。

$f_{i,j}$ 的计算和 $P$ 的计算是一体的，考虑 $x$ 的重链从他的儿子 $y$ 继承。枚举重链长度 $i$，则 $f_{x,i+1}\gets \sum_{j}f_{y,i}\times h_{x,j}\times \frac{i}{i+j}$，其中 $h_{x,j}$ 表示 $g_{x,j}$ 在不考虑 $y$ 这个儿子的情况下的背包数组。

$f_{i,j}$ 的计算可以通过预处理所有儿子实际上的长链之和，用树上背包的方法做到 $O(n^2)$，逆元直接预处理 $1\sim n$ 的即可。问题在于如何快速求 $h$。

方法一：记录 $v_1,v_2,\dots,v_k$ 的前缀背包和后缀背包，求 $h$ 只需要暴力卷积前后缀即可，复杂度为 $O(n^3)$。

方法二：考虑优化上面的过程，用 NTT 算法做卷积，时间复杂度为 $O(n^2\log n)$。

方法三：考虑分治算法，设分治到区间 $[l,r]$ 表示不考虑区间 $[l,r]$ 内所有元素时的 $h$，如果要分治处理 $[l,mid]$ 就将 $[mid+1,r]$ 的信息加到 $h$ 上，再丢到 $[l,mid]$ 处理，$[mid+1,r]$ 同样如此，常数较小，时间复杂度为 $O(n^2\log n)$。

方法四：上述三种算法都将除法变成乘法处理，考虑直接用除法，用 $g_x$ 除去 $f_y$。对于两个多项式 $F,G$（$F$ 为 $G$ 的倍数），他们的次数分别是 $l_1,l_2$（$l_1>l_2$），则 $\frac{F}{G}$ 的次数为 $l_1-l_2$，可以模拟竖式除法的过程，暴力除法的时间复杂度为 $l_2(l_1-l_2)$。不难发现，这个形式也及其类似树上背包的时间复杂度分析（每个点对会贡献一次），所以直接暴力除就可以了，每次只需要对 $f_y$ 的最高次项求逆元即可。时间复杂度为 $O(n^2)$。

此时，就解决了这道题目的所有问题，做到了 $O(n^2)$ 的时间复杂度。官方数据疑似放了很多 $O(n^3),O(n^2\log n)$ 的解法过去（后者几乎全过了）。

一、思路

首先对于公式我们可以注意到：

$t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$

$\forall k \space (1 \leq k \leq m)$ 如果要对答案有贡献就要使 $s$ 的第 $k$ 列的第 $l$ 行到第 $r$ 行都是相同的数

 为什么呢

 如果当前第 $k$ 列对答案的贡献为 $0$

那么显而易见 $xor$ 前后两个式子都必须全为 $1$ 或全是 $0$，考虑全为 $0$ 的情况，对于前一个式子可能 $l \sim r$ 行全是 $0$ 或两种数都有，思考一下就能发现只有当两种数都有的时候才会使答案的贡献为 $0$。

再考虑一下如果前后两个式子全为 $1$，那么对于前一个式子就必须使 $l \sim r$ 行都为 $1$，但显然不可以的，所以就不再考虑。

综上所述如果想让当前第 $k$ 列对答案的贡献为 $1$ 那么 $l \sim r$ 每一个数都为同一种（$0$ 或 $1$）

二、实现

第一关

想必如果理解了以上思路，就很容易想到前缀和（似乎可以用树状数组（doge）），具体怎么实现也很简单根据题目数据会发现一个很奇妙的东西 $nm \leq 1e7$ 这意味着如果我们在主函数中直接定义并初始化时间复杂度是 $O(nm)$ 的！这样便可以建立数组而不超时了。

接下来定义数组 $sum_i,_j$ 表示第 $j$ 列，$1 \sim i$ 的行的前缀和，那么查询时只需要判断 $sum_{l -1},_j \space - \space sum_r,_j$ 是否全为 $0$ 或全为 $1$ 就行了

第二关

还有第二关，发现 $k$ 最大为 $2 * 10^6$ 这是很大的，意味着我们的查询 $l,r$ 完全有可能重复！所以我们可以用 hash 来优化一下（当然一些别的优化，例如：循环节优化 也可以），将每一个 $l,r$ 都变为 $1$ 个 $n$ 进制数，具体为 $l * n + r$，将转化后的数扔进 $map$（当然要用 $unordered \space map$ 优化），每次看 $l,r$ 是否重复即可

第二种实现

即二分做法，我会用另外一篇题解讲述。

一、 初始思路（第一反应）

• 直觉解法：

[线段覆盖模板]

二、 优化过程

• 思路：

首先我们会发现$2$个性质：
1:小A可以到达的点一定是连续的包含x的线段

2:此题即为求解小A可以到达的最大的线段中包含的关键车站




如何求解最大线段？

设最左端点为$1$,最右端点$r$

向左，发现到点i时，设$a_{i}$为以点$i$为终点的轨道中起点的编号最小值。用$a_{i}$更新$l$

向右同理

• 复杂度： 时间O($n$), 空间O($n$)

应该是最快的，现在是最优解

首先：暴力！40分

 略，大家都会

但是 暴力的另一个用处：打表！

 为什么打表呢？

 因为$2≤n,k≤10^{12}$。

 所以时间是O(1)。

 要找数学规律。

 打表：（输出的是没有被淘汰的人）

6 2  

1 2 3 4 5 6  

2 4 6  

4

8 3

1 2 3 4 5 6 7 8

2 3 5 6 8

3 5 8

5 8

8

注意到：每次剩下人中第一个人是有规律的，而且到最后一定只剩一个人（也是当前剩余人中的第一个），更重要的是，这个人的编号就是我们求的答案！！! 

设每次的第一个人依次是$x_1$,$x_2$,$x_3$,......,$x_m$。m是轮数。

则有$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$。

（这个需要自己找）

于是初始$x_1=1$ ，然后往后找。

#include<iostream>

using namespace std;

long long ans,n,k;//ans就是x

int main(){

   scanf("%lld%lld",&n,&k);

   ans=k;//前k个是依次作开头的，所以从k开始也一样

   while(ans+(ans+k-2)/(k-1)<=n){

       ans+=(ans+k-2)/(k-1);//套公式

   }

   printf("%lld",ans);//最后的开头就是最后一个人

   return 0;

}

嗯。于是就过关了！

But，洛谷上有个大佬出了个Hack，几乎把当时所有AC干成UAC了，这份代码也不例外。

就是这个  

1000000000000 10000000000

999999999907

会超时。  

分块优化：

于是我们继续想：每一轮都是一个人一个人淘汰的，所以我们对这一点进行优化…… 

因为$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$ ，所以按$k-1$分块（$k-1$分母，按$x_i$与$k-1$的关系分块，这样每个块的跳跃次数都是一样的)，批量跳跃被淘汰数。  

将整个数域$[1,n]$按每块$k−1$个数划分成若干块：  

第 $1$ 块：$[1,k−1]$  

第 $2$ 块：$[k,2(k−1)]$  

第 $id$ 块：$[(id−1)(k−1)+1,id(k−1)]$  

同一区块内的被淘汰数，递推的步长$\lceil \frac{x_i}{k-1} \rceil$是固定的（等于块编号 $id$），因此可以批量计算该块内的所有被淘汰数，一次跳跃，无需逐个计算。

在第$id$块中，$\lceil \frac{x_i}{k-1} \rceil$（$x$ 属于第 $id$ 块），因此递推式简化为：$x_{next}=x+id$

这意味着在第 $id$ 块中，被淘汰数是以$id$为步长递增的，可以直接计算出该块内最后一个被淘汰数，一次跳到下一块，大幅减少计算次数。

正片开始

#include<iostream>

#include<cstdio>

#include<cmath>

#define ll long long

using namespace std;

ll n,k;

ll x=1,last_val;//x为当前待检查的被淘汰数，初始为第一个被淘汰数x1=1

//last_val是当前块中最后被淘汰的数（答案），不断更新，最终输出

int main(){

   scanf("%lld%lld",&n,&k);

   while(x<=n){

       ll id=(x-1)/(k-1)+1;//是当前x所在块的编号

       ll end=min(n,(k-1)*id);//当前块的末尾

       x+=((end-x)/id+1)*id;//直接跳到当前块的末尾或跳出当前块

       last_val=x-id;//计算当前块最后一个淘汰的数，也可能是所有之中的最后一个淘汰的数（即答案）

   }

   printf("%lld",last_val);

   return 0;

}

OK

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19651912

大意

现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件：

$$1 \leq i + j \leq R,i \geq j \geq 1$$

使对方无法操作者即为胜者。

思路

我们首先考虑这个玩意的 $SG$ 函数，太坑了，你们可以手动的模一下。

我们来假设 $R = 5$ 的情况，首先 $SG(0) = 0$，$SG(1) = 1$，$SG(2) = 2$，但是我们发现，当 $i = 3$ 的时候，能取的只有 $1, 2$，取这两坨只会把必胜态留给对面，那这个时候的 $SG(3) = 0$，那再看 $SG(4) = 1$，然后 $SG(5) = 0$，当 $i \ge R$ 的时候 $SG(i) = 0$，这是显然的。

我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 $i \le \lfloor \frac{R}{2} \rfloor$ 的时候，$SG(i) = i$，实际上就是简单的 Nim 博弈，但是一旦到达 $\lfloor \frac{R}{2} \rfloor + 1$，则 $SG(\lfloor \frac{R}{2} \rfloor + 1) = 0$，这是巧合吗？显然不是，但是只有这一个转折点吗？

我赛时最初的思路是 $SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}$，可是真的对吗？不难发现当 $R = 100$ 时，转折点在 $\lfloor \frac{R}{2} \rfloor + 1 = 51$，但是当 $i = 76$ 的时候呢？我们只能取 $24$，也就是只能取到 $[52, 75]$ 这个区间，而这个区间的 $SG$ 是 ${1, 2, 3, \cdots 24}$，所以 $SG(76) = 0$，所以我刚刚的结论是错误的，继续向后模拟，发现在 $SG(89) = 0$，不难发现，什么时候等于 $0$ 呢，我们设 $pos$ 表示上次的位置，那么有：

$$nxt = \lfloor \frac{pos + R}{2} \rfloor + 1$$

这个说明了，我们的 $SG$ 是一段一段的，最多有 $\log$ 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，$\mathcal{O}(1)$ 处理询问即可。

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define ll long long
const int MAXN = 64;
ll R, lst[MAXN], val[MAXN];
int cnt;

inline ll Xor(ll n){
	switch(n % 4){
		case 1:
			return n - 1;
		case 2:
			return 1;
		case 3:
			return n;
		default:
			return 0;
	}
}

void init(ll x){
	cnt = 0;
	lst[0] = 0;
	ll now = x / 2 + 1;
	val[0] = Xor(now);
	while(now < x){
		lst[++ cnt] = now;
		ll nxt = (now + x) / 2 + 1;
		val[cnt] = val[cnt - 1] ^ Xor(nxt - now);
		now = nxt;
	}
}

ll ask(ll p){
	int idx = upper_bound(lst, lst + cnt + 1, p) - lst - 1;
	return (idx ? val[idx - 1] : 0) ^ Xor(p - lst[idx] + 1);
}

int main(){
	// freopen("orange.in", "r", stdin);
	// freopen("orange.out", "w", stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	int T; cin >> T;
	while(T --){
		string op; cin >> op;
		if(op == "change"){
			cin >> R; init(R);
		}
        else{
			int n; cin >> n;
			ll ans = 0;
			while(n --){
				ll l, r; cin >> l >> r;
				ans ^= ask(r) ^ ask(l - 1);
			}
			cout << (ans ? "1" : "0");
		}
	}
	return 0;
}