【2019浙江省赛 - B】Element Swapping（思维，数学）

题干：

DreamGrid has an integer sequence  and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements  and  () in the sequence when DreamGrid wasn't at home. When DreamGrid comes back, he finds with dismay that his precious sequence has been changed into !

What's worse is that DreamGrid cannot remember his precious sequence. What he only remembers are the two values

Given the sequence after swapping and the two values DreamGrid remembers, please help DreamGrid count the number of possible element pairs  BaoBao swaps.

Note that as DreamGrid is poor at memorizing numbers, the value of  or  might not match the sequence, and no possible element pair can be found in this situation.

Two element pairs  () and  () are considered different if  or .

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains three integers ,  and  (), indicating the length of the sequence and the two values DreamGrid remembers.

The second line contains  integers  (), indicating the sequence after swapping. It's guaranteed that  and .

It's guaranteed that the sum of  of all test cases will not exceed .

Output

For each test case output one line containing one integer, indicating the number of possible element pairs BaoBao swaps.

Sample Input

2
6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3

Sample Output

2
0

Hint

For the first sample test case, it’s possible that BaoBao swaps the 2nd and the 3rd element, or the 5th and the 6th element.

解题报告：

两数作差不难发现，y的差除以x的差，就是a[i]+a[j]，，所以分情况讨论就行了。注意除数为0的情况和x相同y不相同的时候（好坑啊、、）

（%%%wjh大佬）

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
//ll f[1000];
ll a[200000],b[200000];
map<ll,ll> mp;
map<ll,ll> ::iterator it;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		mp.clear();
		ll n,x,y;
		scanf("%lld%lld%lld",&n,&x,&y);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			mp[a[i]]++;
			b[i]=a[i]*a[i];
		}
		ll x2=0,y2=0;
		for(ll i=1;i<=n;i++)
		{
			x2+=a[i]*i;
			y2+=b[i]*i;
		}
		if(x==x2)
		{
			if(y!=y2)
			{
				puts("0");
				continue;
			} 
			ll ans=0;
			for(it=mp.begin();it!=mp.end();it++)
			{
				ll num=it->second;
				ans+=num*(num-1)/2;
			}
			printf("%lld\n",ans);
			continue;
		}
		ll ans=0;
		if(abs(y-y2)%abs(x-x2)!=0)
		{
			puts("0");
			continue;
		}
		ll tmp=(y-y2)/(x-x2);
		ll dx=x-x2;
		ll dy=y-y2;
		for(int i=1;i<=n;i++)
		{
			ll aj=tmp-a[i];
			ll dt=a[i]-aj;
			ll dij;
			if(dt==0)
			{
				continue;
			}
			if(abs(dx)%abs(dt)!=0)
			continue;
			dij=dx/dt;
			ll wj=i+dij;
			if(wj<=i) continue;
			if(aj==a[wj]&&(x==(x2+wj*a[i]+i*a[wj]-i*a[i]-wj*a[wj]))&&(y==(y2-i*b[i]-wj*b[wj]+wj*b[i]+i*b[wj])))
			ans++;
			else
			continue;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
8
6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3
*/