Element Swapping（ZOJ-4101）

Problem Description

DreamGrid has an integer sequence a1,a2,...,an and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements ai and aj (1<=i<j<=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 a1,a2,...,ai-1,aj,ai+1,...,aj-1,ai,aj+1,...an

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 (ai,aj) BaoBao swaps.

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

Two element pairs (ai,aj) (1<=i<j<=n) and (ap,aq) (1<=p<q<=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<=n<=10^5,1<=x,y<=10^18), indicating the length of the sequence and the two values DreamGrid remembers.

The second line contains n integers b1,b2,...,bn (1<=bi<=10^5), indicating the sequence after swapping. It's guaranteed that

 and

.

It's guaranteed that the sum of n of all test cases will not exceed 2*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

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 組資料，每組給出 n 個數的序列和 x、y，現在這個序列中兩個數可能被交換了， x、y 的值是交換前的值，并且計算方式已經給出，問原序列中可能交換的數的對數

思路：

假設交換了 (i,j)，那麼：i*a[i] -> i*a[j]，j*a[j] -> j*a[i]

是以對于原來的 x、y 有：

可以得到：

将得到的兩個式子相除，有：

然後根據式子左端 

 的內插補點去分析 x、y 的取值，進行讨論即可

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;

struct Node {
    LL val,id;
    bool operator<(const Node &rhs)const {
        return val<rhs.val;
    }
} a[N];
int vis[N];
int main() {
    int t;
    scanf("%d",&t);
    int Case=1;
    while(t--) {
        LL n,x,y;
        scanf("%d%lld%lld",&n,&x,&y);
        for(int i=1; i<=n; i++) {
            vis[i]=0;
            scanf("%lld",&a[i].val);
            x-=(LL)i*a[i].val;//記錄x內插補點
            y-=(LL)i*a[i].val*a[i].val;//記錄y內插補點
            a[i].id=i;
        }

        sort(a+1,a+n+1);

        LL res=0;
        if(x==0&&y!=0)//內插補點相除為0，說明沒有交換
            printf("0\n");
        else if(y%x)//內插補點可以整除，說明沒有交換
            printf("0\n");
        else if(x==0&&y==0) {//x、y的內插補點為0說明交換後值未變
            for(int i=1; i<=n; ) {
                LL temp=0;
                int j=i;
                for( ; j<=n; j++) {
                    if(a[i].val!=a[j].val)//值不相同時不再統計
                        break;
                    temp++;//可能情況數
                }
                res+=(temp*(temp-1))/2;//累計個數
                i=j;
            }
            printf("%lld\n",res);
        }
        else {
            int pos=1;//位置
            LL quotient=y/x;//內插補點的商
            int i=1,j=n;
            while(i<j) {//雙指針前後同時枚舉
                pos++;
                int k=i;
                while(k<j&&2*a[k].val==quotient&&a[k].val==a[i].val)
                    k++;

                if(i!=k) {
                    i=k;
                    continue;
                }

                while(j>i&&a[j].val+a[i].val>quotient)
                    j--;

                if(j==i)//枚舉結束
                    break;

                if(a[i].val+a[j].val!=quotient) {//兩數相加後不等于商
                    i++;
                    continue;
                }
                if(x%(a[j].val-a[i].val)!=0) {//無法整除x的餘數
                    i++;
                    continue;
                }


                LL num=x/(a[j].val-a[i].val);
                k=i;
                while(k<j&&a[k].val==a[i].val) {
                    if(a[k].id-num<=n&&a[k].id-num>0)
                        vis[(int)a[k].id-(int)num]=pos;
                    k++;
                }
                while(j>=k&&a[i].val+a[j].val==quotient) {
                    if(vis[a[j].id]==pos)
                        res++;
                    j--;
                }

                i=k;
            }
            printf("%LLd\n",res);
        }
    }
    return 0;
}