题解 P5497 【[LnOI2019SP]龟速单项式变换(SMT)】

QAQ我比赛的时候居然煞笔了没想出正解……

我比赛的时候不想动脑子，这样打的：

#include <bits/stdc++.h>
using namespace std;
int main(){puts("YES");}

70。。。

其实，大家想一下，如果$n<m$，则肯定能构造一组数据，因为$x%m$的余数就有$m-1$种，所以必然能构造出一组数据。

于是得出结论1： $n<m$时，答案为NO

那么我们可以大胆猜想，不用证明，$n≥m$时一定就是YES了

好吧我们来证一下

根据抽屉原理，当$n≥m$时，必然有一个余数出现了2次

设这两个余数相同的数分别为$x_i,x_j$，可以以$x_i$为一个元素构造出一个“司$m$序列”，于是有：

$$ (sum_{1}+x_i)-(sum_{2}+x_j)\equiv 0(mod m) $$

进一步：

$$ sum_{1}+x_i\equiv sum_{2}+x_j (mod m) $$

又因为

$$ x_i\equiv x_j (mod m)$$

所以

$$ sum_{2}\equiv 0(mod m) $$

于是可以针对$x_j$构造出一个“司$m$序列”。

命题得证。

于是得到结论：

$n<m$时，答案为NO；否则为YES

代码就不贴了，讲的这么清楚了应该都能自己写出来