OI - Coins(Codeforces)

日常看不出势能函数题……（瞎手玩玩到十二点 qwq）

---

# 题面

> Linked Codeforces-1423F

点击展开/折叠题面

有 $n$ 个人围成一个圆桌，依次编号为 $1$ 到 $n$（$1\le n\le10^9$）。其中有 $m$ 个人一开始就有硬币（$1\le m\le2\times10^5$），第 $i$ 个一开始就有硬币的人编号为 $a_i$，有 $b_i$ 枚硬币。

接下来进行若干回合，每个回合选择一个有大于等于两个硬币的人，他会给他旁边的两个人每人一个硬币。你需要判断能否在有限的回合内使得每个人的硬币数都不超过 $1$。

---

# 解析

手玩几次，我们可以发现，设总共有 $k$ 枚硬币：

• 若 $k>n$，显然无法做到；
• 若 $k<n$，似乎都可以做到；
• 若 $k=n$，不一定可以做到。

既然是势能函数题，直接给出势能函数的定义，一枚硬币的势能值为其所在的人的 id（所在位置）。然后我们发现，设一个回合中指定的人为 $i$，则被分出去的两个硬币的势能值之和在模 n 意义下不变（一个加一、另一个减一）。

于是我们知道，起始状态和终止状态的势能函数值相同。只要存在一个结束状态的势能函数值与起始状态相同，则可以实现。

然后就可以解释为什么 $k<n$ 时一定可以实现了，考虑解释状态的势能函数值为 $(x_1+x_2+\dots+x_k)\bmod n$，其中 $x_1,x_2,\dots,x_k\in[0,n-1]$ 是互不相同的数，当 $k<n$ 时

$$x_1+x_2+\dots+x_k\equiv m\pmod n$$

对任意 $m$ 都有解，所以对任意起始状态都可以找到势能函数值相同的结束状态。

但是 $k=n$ 时，只有一种结束状态，即填满；那么起始状态的势能函数值就必须一样。

所以算一下就好了……

- Update: 等价性证明

（上面的只有必要性没有充分性 :( ） TLY NBBBBBBBBBB!!!!!!!!!!

为了方便书写，以下证明的下标自动转化为 $[1,n]$ 内（eg. $i=1$ 时，$b_{i-1}$ 表示 $b_n$）

另外 $b_i$ 重新定义为编号为 $i$ 的人的初始硬币数。

假设有解，且对第 $i$ 个人的“拟操作次数”为 $c_i$（不一定是真的操作次数），则有

$$0\le b_i-2c_i+c_{i-1}+c_{i+1}\le1$$

设“拟终止状态”时第 $i$ 个人有 $x_i=b_i-2c_i+c_{i-1}+c_{i+1}$ 枚硬币。

首先证明，“存在 $\{c_i\}$ 的非负整数解”$\Leftrightarrow$“有合法解”，考虑归纳证明：

• 若 $c_i$ 均为 $0$，则已经合法，此时“拟操作次数”就是真实的操作次数；

• 如果 $\exists c_i\neq 0$ 的 $i$ 对应的 $b_i\geq 2$，归纳；否则：

  • $\forall c_i\neq0$，有 $b_i\le1$；
  • $\forall c_i=0$，有 $0\le b_i-2c_i+c_{i-1}+c_{i+1}\le1$ ，则 $0\le b_i+c_{i-1}+c_{i+1}\le1$；因为 $c_{i-1}\ge0$ 且 $c_{i+1}\ge0$，所以 $b_i\le1$；

  我们惊奇地发现此时已经合法了，剩下的操作可以不进行，则我们通过这个“拟操作次数”得到了一个合法的操作方案。

定义 $d_i=c_i-c_{i-1}$，则 $x_i=b_i-d_i+d_{i+1}$ 然后可以推出 $d_{i+1}=d_i+x_i-b_i$，再代入若干次，可以得到：

$$\begin{aligned} d_i&=d_{i-1}+x_{i-1}-b_{i-1}\\ &=d_{i-2}+x_{i-2}-b_{i-2}+x_{i-1}-b_{i-2}\\ &=\cdots\\ &=d_1+\sum_{j=1}^{i-1}(x_j-b_j) \end{aligned}$$

根据 $d_i=c_i-c_{i-1}$，直接代入可得 $\sum d_i=0$，而

$$\begin{aligned} \sum_{i=1}^n d_i&=nd_1+\sum_{i=1}^n\sum_{j=1}^{i-1}(x_j-b_j)\\ &=nd_1+\sum_{i=1}^n(n-i)(x_i-b_i) \end{aligned}$$

因为 $d_1,x_i,b_i$ 都是整数，于是有

$$\begin{aligned} nd_1+n\sum_{i=1}^n(x_i-b_i)-\sum_{i=1}^ni(x_i-b_i)&=0\\ \sum_{i=1}^ni(x_i-b_i)&\equiv0&\pmod n\\ \sum_{i=1}^nix_i&\equiv\sum_{i=1}^nib_i&\pmod n \end{aligned}$$

等式左边是结束状态的势能函数值，右边是初始状态势能函数值；注意到 $\{x_i\}$ 是我们定义的一个“拟终止状态”，尽管不一定能够从初始状态得到，但是它仍然满足终止状态“每个人的硬币都不超过一枚”的性质，所以与前文势能函数的结论“只要存在一个结束状态的势能函数值与起始状态相同，则可以实现”相吻合。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m;
long long tot,fun;

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}
int main(){
	n=Read(),m=Read();
	for(int i=1;i<=m;i++){
		int pos=Read(),cnt=Read();
		tot+=cnt;
		fun+=1ll*pos*cnt;
	}
	if(tot<n){printf("1\n");return 0;}
	if(tot>n){printf("-1\n");return 0;}
	if(fun%n==n*(n+1ll)/2%n) printf("1\n");
	else printf("-1\n");
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &且休去\\ &听风鉴凶吉观星即观心\\ &更高处不及\ 闻一道可矣\\ &谓我知音\ 同去\\ &下世一聚\ 再起一局\ ”\\ ——&\text{《不可道》 By 赤羽/忘川风华录} \end{split}$$

> Linked 不可道-网易云