题目传送门
题目大意
给定将$\left \{ 0, 1, \dots, m - 1\right \}$分成了不相交的两个非空集合$A$和$B$，给定$A$，问存在多少个整数$x$满足$0\leqslant x < m$且对于任意$a\in A, b \in B$满足$a + b\not \equiv x \pmod{m}$
容易发现满足后一个条件的充分必要条件是对于任意$a \in A$，存在$a' \in A$使得$a + a' \equiv x \pmod{m}$。
如果$a \leqslant x$，则易证$a' \leqslant x$。
同样，如果$a > x$，则易证$a' > x$。
所以这个数$x$将序列分成两部分，每一部分首尾配对后，每一对的和都等于$x$。
那么怎么判断呢？我们发现$a + d = c + b$等价于$a - b = c - d$。
所以我们只用差分一下判断是否是回文，再判断首尾的和是否等于$x$就行了。
Code
/**
* Codeforces
* Problem#1045B
* Accepted
* Time: 77ms
* Memory: 7300k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
typedef bool boolean; #define ull unsigned long long const int N = 2e5 + ;
const ull base = 1e9 + ; int n, M;
int ar[N];
int cr[N];
ull ph[N], sh[N], pb[N]; int add(int a, int b) {
return ((a += b) >= M) ? (a - M) : (a);
} inline void init() {
scanf("%d%d", &n, &M);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} ull fquery(int l, int r) { // forward
if (l > r)
return ;
return ph[r] - ph[l - ] * pb[r - l + ];
} ull rquery(int l, int r) { // backward
if (l > r)
return ;
return sh[l] - sh[r + ] * pb[r - l + ];
} boolean ispar(int l, int r) {
return fquery(l, r) == rquery(l, r);
} vector<int> vec; inline void solve() {
ph[] = , sh[n] = , pb[] = ;
for (int i = ; i < n; i++)
ph[i] = ph[i - ] * base + (cr[i] = ar[i + ] - ar[i]);
for (int i = n - ; i; i--)
sh[i] = sh[i + ] * base + cr[i];
for (int i = ; i < n; i++)
pb[i] = pb[i - ] * base; for (int i = , x; i < n; i++) {
x = ar[] + ar[i];
// if (x >= M)
// break;
if (add(ar[i + ], ar[n]) == x && ispar(, i - ) && ispar(i + , n - ))
vec.push_back(x);
}
int x = add(ar[], ar[n]);
if ((x <= ar[] || x >= ar[n]) && ispar(, n - ))
vec.push_back(x);
printf("%d\n", (signed) vec.size());
sort(vec.begin(), vec.end());
for (int i = ; i < (signed) vec.size(); i++)
printf("%d ", vec[i]);
putchar('\n');
} int main() {
init();
solve();
return ;
}