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:

5

10

3

1

1

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);
}
05-19 16:41
查看更多