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