P3909 异或之积

为什么叫做异或之积？

答曰：只要不关乎Alice和Bob就行

做完这道水题，感觉自己弱爆了。

一开始就要考虑暴力\(O(n^3)\)的优化。

然后就注意到了题目中的\(6\)为什么不是⑨

然后就想到了全排列，然后根据全排列瞎搞了一波。

如下：

注意到\(A_i*A_j*A_k=A_j*A_k*A_i\)，然后三个元素的全排列个数就是6

然后题意转变为从一堆数中，不重复，不遗漏的选出三个元素，求出所有三元组的积的和

怎么实现呢？

一开始就是\(O(N^3)\)的暴力

然后发现可以利用前缀和的思想，将后两个数的乘积算出来，在前缀和一下。然后在\(O(N)\)的枚举第一个数，利用前缀和计算出和

然后又可以使用类似的思想，将那个\(O(N^2)\)的预处理也变成\(O(N)\)的。

但是

我调了好久，还是没有gan出来。

然后看了看其他人的code。发现

我们只要处理出三个前缀和就行了。

代码如下

#include<cstdio>

#include<algorithm>

#include<iostream>

const int maxn=1000010;

const long long mod=1e9+7;

int s[maxn];

int S[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    long long pas;

    long long ans=0;

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&pas);

        s[i]=(s[i-1]+pas)%mod;

        S[i]=(S[i-1]+pas*s[i-1])%mod;

        ans=(ans+pas*S[i-1])%mod;

    }

    pas=ans;

    for(int i=1;i<=5;i++)

        ans=(ans+pas)%mod;

    printf("%lld",ans);

}

真的是纯真不做作。吐血emmm

发现自己口胡了一波看似正解的东西，被一波code技巧打败了。

sad

巴特西

P3909 异或之积

但是

最新文章

热门文章