SPOJ：Just One Swap（统计&思维）

You are given an array of size N. How many distinct arrays can you generate by swapping two numbers for exactly once? The two selected numbers can be equal but their positions in the array must be different.

Input

The first line of the input contains a single integer T, denoting the number of test cases. Every test case starts with an integer N. The next line contains N integers, the numbers of the array.

Output

For each tescase output the answer in a single line.

Constraints:

1 <= T <= 5

1 <= Value of a number in the array <= 100000

2 <= N <= 100000

Example

Input:

1
5
2 3 2 3 3

Output:

7

You can generate the following arrays:

2 3 2 3 3

2 2 3 3 3

2 3 3 2 3

2 3 3 3 2

3 2 2 3 3

3 3 2 2 3

3 3 2 3 2

题意：问给定一个数论，问交换两个位置上的数，可以变成多少个新的数组（重复的只统计一次）。

思路：先考虑变后与原来数论不同：对于每个位置，可以和与此数不同的位置交换，每一种合法交换统计了两次，最后除二。

如果某个数出现的次数大于1，则可以产生与原数论相同的数列。ans++；

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int a[maxn],num[maxn];

long long ans=;

int main()

{

    int N,T,i,j; bool F;

    scanf("%d",&T);

    while(T--){

        memset(num,,sizeof(num));

        scanf("%d",&N); ans=; F=false;

        for(i=;i<=N;i++){

            scanf("%d",&a[i]);

            num[a[i]]++;

        }

        for(i=;i<=N;i++){

            if(num[a[i]]>) F=true;

            ans+=(N-num[a[i]]);

        }

        ans>>=1LL;

        if(F) ans++;

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

SPOJ：Just One Swap（统计&思维）

Input

Output

Constraints:

Example

最新文章

热门文章