Element Swapping
Time Limit: 1 Second Memory Limit: 65536 KB
DreamGrid has an integer sequence $a_1,a_2,a_3,\dots ,a_n$ and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements $a_i$ and $a_j$ $(1\le i<j\le n)$ 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 $a_1,a_2,\dots ,a_{i?1},a_j,a_{i+1},\dots ,a_{j?1},a_i,a_{j+1},\dots ,a_n$

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

$x={\sum }_{k=1}^{n}k{a}_k\text{and}y={\sum }_{k=1}^{n}k{a}_k^2$

Given the sequence after swapping and the two values DreamGrid remembers, please help DreamGrid count the number of possible element pairs $(a_i,a_j)$ 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 $(a_i,a_j)(1\le i<j\le n)$ and $(a_p,a_q)(1\le p<q\le n)$ are considered different if $i=?p$ or $j=?q$.

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

The first line contains three integers $n$,$x$ and $y$ $(2\le n\le 10^5,1\le x,y\le 10^{18})$, indicating the length of the sequence and the two values DreamGrid remembers.

The second line contains $n$ integers $b_1,b_2,\dots ,b_n(1\le b_i\le 10^5)$, indicating the sequence after swapping. It’s guaranteed that ${\sum }_{k=1}^{n}k{b}_k\le 10^{18}$ and ${\sum }_{k=1}^{n}k{b}_k^2\le 10^{18}$.

It’s guaranteed that the sum of of all test cases will not exceed $2\times 10^6$.

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.

題目大意：
第一行輸入一個整數$t$，代表有$t$組測試樣例，對于每組測試樣例，先輸入三個整數$n,x_1,y_1$，下一行再輸入$n$個整數的數組$a_1,a_2,\dots ,a_n$$(1\le a_i\le 10^5)$，現在我們能交換數組中的任意兩個元素$a_i$和$a_j$ $(1\le i<j\le n)$，使得改變后的數組求得的$x,y$變為$x1,y1$，問有多少種交換方案。
解題思路：
通過題意我們可以知道，此題相當于我們可以根據公式$x={\sum }_{k=1}^{n}k{a}_k$ 和 公式$y={\sum }_{k=1}^{n}k{a}_k^2$求出當前數組的$x$和$y$，我們可以將其記作$x_2,y_2$，交換數組中的兩個元素后的$x,y$為$x_1,y_2$，因為我們僅交換了數組中的兩個元素，所以根據$x,y$的公式，我們可以知道$x_1,x_2$的區別在于$x2$中$a_i,a_j$兩項為$i{a}_i+j{a}_j$，而$x1$也就是交換后$a_i,a_j$兩項為$j{a}_i+i{a}_j$，其他項完全相同，所以可以得到$x2?x1=(i?j)(a_i?a_j)$，同理$y2?y1=(i?j)(a_i^2?a_j^2)$即$y_2?y_1=(i?j)(a_i?a_j)(a_i+a_j)$。
因此可以先假設$x=x_2?x_1,t=y_2?y_1$，如果$x==0\&\&y==0$的話，那么則證明$a_i==a_j$，則方案數則為數組中選取任意兩個相同項的方案數，例如假設$a$在數組中出現了$k$次，則$ans+=C_k^2$。
若$x=?0\&\&y=?0$，通過$x=(i?j)(a_i?a_j)$和$y=(i?1)(a_i?a_j)(a_i+a_j)$，可知$y/x=a_i+a_j$，這是就可以判斷一下若$y\%x==0$則存在，否則$ans=0$，因此可以得到$a_i+a_j$的值，此時就可以通過遍歷數組$a[]$，求出其對應的$a[j]$，通過遍歷可以確定$i,a[i],a[j]$的值，然后根據$x=(i?j)(a_i?a_j)$，可以求出$j$，這時只需判斷數組中的第$j$項是否為$a[j]$，若是則方案數加一。
代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
ll arr[100100];
ll num[100100];
set<ll> s;
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;scanf("%d",&t);while(t--) {int n;ll x1,x2=0,y1,y2=0;scanf("%d %lld %lld",&n,&x1,&y1);s.clear();memset(num,0,sizeof num);rep(i,1,n) {scanf("%lld",&arr[i]);x2+=(ll)i*arr[i];y2+=(ll)i*arr[i]*arr[i];s.insert(arr[i]);num[arr[i]]++;}ll x=x2-x1,y=y2-y1;ll ans=0;if(x==0&&y==0) {for(auto it=s.begin();it!=s.end();it++) {if(num[*it]>1) {ans+=(num[*it]*(num[*it]-1))/2LL;}}}else if(x!=0&&y!=0) {if(y%x==0) {ll t=y/x;for(int i=1;i<=n;i++) {if(t-arr[i]>0&&t-arr[i]<=100000&&num[t-arr[i]]>0) {ll nape=arr[i]-(t-arr[i]);if(nape!=0&&x%nape==0) {int k=i-x/nape;if(k>i&&k<=n&&arr[k]==t-arr[i]) ans++;}}}}else ans=0;}else ans=0;printf("%lld\n",ans);}return 0;
}