# quhengyi11 的博客

### 题解 CF1045I 【Palindrome Pairs】

posted on 2019-04-12 19:43:21 | under 题解 |

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 998244353
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
int n;
struct node{
int nxt, v, cnt;
}e[N << 1];
int tmp[26];
char ch;
ll ans;
{
memset(tmp, 0, sizeof tmp);
ch = getchar();
while (!isalpha(ch)) ch = getchar();
while (isalpha(ch)) ++tmp[ch - 'a'], ch = getchar();
fo (i, 0, 25) x = (x << 1) | (tmp[i] & 1);
}
int now, x;
int main ()
{
scanf("%d", &n);
fo (i, 1, n) { read(a[i]); u[i] = a[i]; }
std::sort(u + 1, u + n + 1);
fo (i, 1, n)
{
ans += std::upper_bound(u + 1, u + n + 1, a[i]) - std::lower_bound(u + 1, u + n + 1, a[i]) - 1;
fo (j, 0, 25)
{
now = a[i] ^ (1 << j);
x = std::upper_bound(u + 1, u + n + 1, now) - std::lower_bound(u + 1, u + n + 1, now);
ans += x;
}
}
printf("%lld", ans >> 1);
}