20181030NOIP模拟赛T3

2017种树

2017共有N棵树从0到N-1标号。现要把这些树种在一条直线上，第i棵树的种植位置X[i]如下确定：

X[0] = X[0] MOD L；

X[i] = (X[i-1]*A+B) MOD L。

每棵树种植的费用，是所有标号比它小的树与它的距离之和。2017请你计算各棵树的费用之积，最后对1000000007取余。

输入：

共五行：

第一行为N

第二行为L

第三行为X[0]

第四行为A

第五行为B

输出：

总费用

Input1:

Output1:

180

样例解释：

5棵树的位置分别为: 3, 4, 5, 6, 7.

费用分别为: 1, 3, 6, 10. （从第一棵树开始）

总费用为： 1 × 3 × 6 × 10 = 180.

数据范围：

10%的数据：N<=10;

60%的数据：N<=5×10^4;

100%的数据：N,L<=200000; X[0] ,A, B<=10^9.

思路：

权值线段树好题

一个点和他前面某个点的距离

等于这个点坐标减去前面那个点的坐标

那么，前面所有点到这个点的距离和

等于前面这些点的数量*当前点坐标-前面点的坐标和

对于这个问题，我们开一颗权值线段树维护即可

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rs 262143

#define p 1000000007

#define rii register int i

#define rij register int j

#define int long long

using namespace std;

long long n,l1,y[],a,b,ans;

struct tree{

    long long cnt,sum;

}x[rs*];

void add(int wz,int l,int r,int bh)

{

    if(wz==l&&wz==r)

    {

        x[bh].cnt++;

        x[bh].sum+=wz;

        return;

    }

    int mid=(l+r)/;

    if(wz<=mid)

    {

        add(wz,l,mid,bh*);

    }

    else

    {

        add(wz,mid+,r,bh*+);

    }

    x[bh].cnt=x[bh*].cnt+x[bh*+].cnt;

    x[bh].sum=x[bh*].sum+x[bh*+].sum;

}

tree query(int l,int r,int nl,int nr,int bh)

{

    if(l<nl)

    {

        l=nl;

    }

    if(r>nr)

    {

        r=nr;

    }

    if(nl==l&&nr==r)

    {

        return x[bh];

    }

    int mid=(nl+nr)/;

    tree kkk;

    tree lzn;

    lzn.cnt=,lzn.sum=,kkk.sum=,kkk.cnt=;

    if(l<=mid)

    {

        kkk=query(l,r,nl,mid,bh*);

    }

    if(r>mid)

    {

        lzn=query(l,r,mid+,nr,bh*+);

    }

    kkk.cnt+=lzn.cnt;

    kkk.sum+=lzn.sum;

    return kkk;

}

signed main()

{

    freopen("gg.in","r",stdin);

    freopen("gg.out","w",stdout);

    scanf("%lld%lld%lld%lld%lld",&n,&l1,&y[],&a,&b);

    y[]%=l1;

    add(y[],,rs,);

    ans=;

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

    {

        long long an=;

        y[i]=(y[i-]*a+b)%l1;

        tree kkk;

        kkk=query(,y[i],,rs,);

        an+=kkk.cnt*y[i];

        an%=p;

        an-=kkk.sum;

        an+=p;

        an%=p;

        kkk=query(y[i],l1-,,rs,);

        an+=kkk.sum;

        an-=kkk.cnt*y[i];

        an+=p;

        an%=p;

        ans*=an;

        ans%=p;

        add(y[i],,rs,);

    }

    printf("%lld\n",ans);

}

巴特西

20181030NOIP模拟赛T3

2017种树

思路：

代码：

最新文章

热门文章