目录
题意：
给你一个n个数的集合a，和整数c
求0~c中有多少对x,y的组合可以使得x+y与y-x都不出现在集合a中。
思路：
我们可以求出总的对数，减去不合法数即可。
由于有两个不合法的条件，我们可以使用*容斥* (减去任意一个不合法的再加上两个都不合法的)
总的对数：
//0 : c+1 x为0时，y可以是0~c的任意一个，有c+1种
//1 : c
//c : 1
// (c+2)*(c+1)/2
x+y==ai:
//0 ai
//1 ai-1
//2 ai-2
//...
// 一共 ai/2 +1 对
(如ai == 7 :
//0+7，1+6, 2+5, 3+4
4种，7/2 == 3下取整, 再加一
y-x == ai:
ai 0
ai+1 1
...
c (c-ai)
一种 c-ai+1 对
两个都不符合：
x+y == ai
y-x == aj
解得：
y = (ai+aj)/2
x = (ai-aj)/2
必须是整数，所以ai+aj是偶数。同时ai也必定大于aj，x也满足。
但总数是多少呢？
其实就是看集合a中多少个奇数对和偶数对。
我们遍历的过程中就能求出来。
统计i之前有多少个奇数cnt1和偶数cnt2即可(包括自己，即ai == aj ，x为0的情况)，a[ i ]是奇数就加cnt1种，偶数则cnt2种。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define int long long
// 7
//1+6,2+5,3+4
//还有0和7！
void solve()
{
int n, c;
cin >> n >> c;
vector<int>arr(n + 1);
for (int i = 1; i <= n; i++)
cin >> arr[i];
sort(arr.begin(), arr.end());
ll ans = (c + 2) * (c + 1) / 2;
int s1, s2, c1, c2, s3;
s1 = s2 = s3 = 0;
c1 = c2 = 0;
for (int i = 1; i <= n; i++)
{
s1 += arr[i] / 2+1;
s2 += c - arr[i] + 1;
if (arr[i] % 2 == 0)
{
c2++;
s3 += c2;
}
else
{
c1++;
s3 += c1;
}
}
cout << ans - s1 - s2 + s3 << endl;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
