一道不那么暴力的枚举题
P3799
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[10001];
int b[10001];
int mem[10001] = {0};
void quicksort(int l,int r){int mid = (l + r) >> 1;if(l >= r) return;quicksort(l,mid);quicksort(mid + 1,r);int cnt = l;int x = l,y = mid + 1;while(x <= mid && y <= r){if(a[x] < a[y]){b[cnt] = a[x];cnt++;x++;}else{b[cnt] = a[y];cnt++;y++;}} while(x <= mid){b[cnt++] = a[x++];}while(y <= r){b[cnt++] = a[y++];}for(int i = l;i <= r;i++){a[i] = b[i];}
}
int main(){int n;cin >> n;int maxn = -0x3f3f3f;for(int i = 1;i <= n;i++){cin >> a[i];mem[a[i]]++;maxn = max(maxn,a[i]);}quicksort(1,n);//cout << endl;long long ans = 0;long long temp;for(int i = maxn;i >= 1;i--){if(mem[i] >= 2){temp = (mem[i]) * (mem[i] - 1) / 2;//cout << i <<" "<< temp << endl;for(int j = i - 1;j >= ceil((double) i / 2.00);j--){if(mem[j] >= 1 && mem[i - j] >= 1 && j != i - j){//ans++;//ans = (ans + 1) % (long long)(1e9 + 7);ans += temp * (mem[i - j]) * (mem[j]);//cout << mem[j] <<" "<< mem[i - j] << " " << ans << endl;ans %= (long long) (1e9 + 7);}else if(mem[j] >= 1 && mem[i - j] >= 1 && j == i - j){//ans++;//ans = (ans + 1) % (long long)(1e9 + 7);ans += temp * (mem[j]) * (mem[j] - 1) / 2;//cout << mem[j] <<" "<< mem[i - j] << " " << ans << endl;ans %= (long long) (1e9 + 7);}}}}cout << ans << endl;
}