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

题目大意：

给你一个由

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)

的。

代码实现：

CPP

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

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

文章操作

相关推荐

评论

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