题解：P12883 [蓝桥杯 2025 国 C] 正方形构造

Liyuqiao11 · 2025-07-10 21:08:40 · 题解

题目大意：

给你一个由 n 个正整数组成的序列 a ，求符合条件的四元组（ i , j , p, q ）满足 i , j , p , q 互不相同且( 0 , 0 )、( -a _ {i} , a _ {j} )、( a _ {p} , a _ {q} )、( a _ {p}-a _ {i} , a _ {j}+a _ {q} )能构成一个正方形的数量，答案对 1e9+7 取模。(1<= n <= 1e6 ,1<= a _ {i} <=1000)

解题思路：

我们首先要先翻译一下题目所给的已知条件。首先令( 0 , 0 )为A点，( -a _ {i} ,a _ {j} )为B点，( a _ {p} ,a _ {q} )为C点，( a _ {p}-a _ {i} , a _ {j}+a _ {q} )为D点。因为( -a _ {i} ) -0 =( a _ {p}-a _ {i} ) -a _ {p} 并且 a _ {j}-0 =( a _ {j}+a _ {q} ) -a _ {q} ，所以BA平行且等于DC，四边形ABCD为平行四边形。若要使四边形ABCD为正方形，则 a _ {i} = a _ {q} 且 a _ {j} = a _ {p} ，这个结论可以用全等或用直线BA的斜率直线CA的斜率为 -1 得出。接下来，最朴素的想法是枚举 i , j , p , q ，再一一检验是否满足条件，但这是 O(n^4) 的，无法通过此题。我们可以转变一个思路，由于 a _ {i} 的上限远远小于 n 的上限，并且我们并不需要去关心究竟是哪些四元组对答案造成了贡献，所以我们可以记录每个数值在 a 序列的数量为 mp _ {i} ，再枚举 a _ {i} 和 a _ {j} 的数值，用题目中样例说明所提示的方法进行一个组合数的计算，如果 a _ {i} != a _ {j} ， $ans+=A{mp {i}}^{2}A{mp {j}}^{2} ，否则ans+=A{mp {i}}^{4} 即可获得最终答案，这是 O(n)$ 的。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M = 1e3+10;
const int md = 1e9+7;
#define int long long
int n,a[N],mp[M],cnt[N],ans;
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(i==j) cnt[i*j]=(cnt[i*j]%md+mp[i]%md*(mp[i]-1)%md*(mp[i]-2)%md*(mp[i]-3)%md)%md;
            else cnt[i*j]=(cnt[i*j]%md+mp[i]%md*(mp[i]-1)%md*mp[j]%md*(mp[j]-1)%md)%md;
        }
    }
    for(int i=1;i<=N-10;i++){
        ans=(ans%md+cnt[i]%md)%md;
    }
    cout<<ans<<endl;
    return 0;
}