每日六题解（五）--珂朵莉与宇宙

首先看数据..n是1e5,而ai只有10..且暴力枚举的话它也告诉你了..有(n+1)n/2种,直接暴力肯定超时..那么我们换种思路..
1.考虑平方数..因为平方数数据肯定是(0~1000^2)那么枚举的复杂度最多n1000当然不会这么大..而且就算这么大,强大的牛客测评机也是过的去的..
2.接下说下枚举的思路..记录每个位子的大小..注意记录的时候不是把那个点记为1..而是+1,因为可能会有0..那么就会有重复了.重复就要+1吧,我先一个数一个数的处理..枚举每个平方数就好了,假如之前出现过这个数,那我ans+cnt[pos-j*j]..
3.贴代码了~

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e5+5;
const int M=1e6+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
int a[N];
int cnt[M];
int main()/*因为数据的ai只有10,n是1e5,所以枚举1~1000的平方数*/
{
    ios;
    ll ans=0,pos=0,n;
    cnt[0]=1;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pos+=x;
        for(ll j=0;j*j<=pos;j++)
        {
            ans+=cnt[pos-j*j];
        }
        cnt[pos]++;
    }
    cout<<ans<<endl;
    return 0;
}