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;
}