题解 P4340 【[SHOI2016]随机序列】
shadowice1984
2018-04-03 21:33:49
线段树好题啊
猜中(分明是严谨而合理的推倒)结论的话,似乎非常简单的样子?
## 那么开始愉快的推倒结论吧~
我们发现一个很奇怪的事实是,这个长度为n的序列只有n-1个运算符号
也就是说,**第一项的系数必为正**
所以我们呢考虑去掉第一项,现在变成了每一位(第一项符号不能为乘)都是任意符号的序列
那么我们发现,在这个符号任意的所有序列当中,对于任意一个序列,加减号反转之后都会存在一个对应的序列与之相对应然后如果我们把这些序列两两配对相加之后总和一定是0(因为每一对相加都是0)
那么此时让我们来看被忽略的首项,显然因为第一项必为正所以肯定是消不掉的
那么我们来枚举这个首项,看看有多少个首项是消不掉的,换句话来讲我们呢统计后边的序列有多少中可能性,假设后边的长度为len,第一个符号显然不可以选乘,其他的任意选,一共有$2×3^n$种可能性,所以我们要对这个首项乘上一个系数就行了
然后我们发现这个首项呢就是序列的前缀积,而我们要维护前缀积的和,发现此时单点修改=前缀积区间乘法,此时我们只需要写一个资瓷区间乘区间求和的线段树就可以完成单点赋值的操作了~
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int m;ll mod=1e9+7;ll mi[N];ll prm[N];ll val[N];//记得写乘法逆元
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=(a*a)%mod){if(p&1){r=(r*a)%mod;}}return r;}
struct linetree//区间乘区间求和的线段树~
{
ll val[4*N];ll mult[4*N];
inline void pushdown(int p)
{
val[p<<1]=val[p<<1]*mult[p]%mod;
val[p<<1|1]=val[p<<1|1]*mult[p]%mod;
mult[p<<1]=mult[p<<1]*mult[p]%mod;
mult[p<<1|1]=mult[p<<1|1]*mult[p]%mod;mult[p]=1;
}
inline void setmul(int p,int l,int r,int dl,int dr,ll mul)
{
if(dl==l&&dr==r){mult[p]=mult[p]*mul%mod;val[p]=val[p]*mul%mod;return;}
int mid=(l+r)/2;pushdown(p);
if(dl<mid){setmul(p<<1,l,mid,dl,min(dr,mid),mul);}
if(mid<dr){setmul(p<<1|1,mid,r,max(dl,mid),dr,mul);}
val[p]=(val[p<<1]+val[p<<1|1])%mod;
}
inline ll getv(){return val[1];}
inline void build(int p,int l,int r)
{
if(r-l==1){val[p]=prm[r];return;}int mid=(l+r)/2;mult[p]=1;
build(p<<1,l,mid);build(p<<1|1,mid,r);val[p]=(val[p<<1]+val[p<<1|1])%mod;
}
}lt;
int main()
{
scanf("%d%d",&n,&m);mi[0]=1;prm[0]=1;
for(int i=1;i<=n;i++){scanf("%lld",&val[i]);}
for(int i=1;i<=n;i++){mi[i]=mi[i-1]*3%mod;}//处理3的幂次
for(int i=1;i<=n;i++){prm[i]=prm[i-1]*val[i]%mod;}//处理前缀积
for(int i=1;i<=n-1;i++){prm[i]=prm[i]*2*mi[n-i-1]%mod;}//乘上对应的系数
lt.build(1,0,n);//构建线段树~
for(int i=1;i<=n;i++)
{
int t;ll v;scanf("%d%lld",&t,&v);
lt.setmul(1,0,n,t-1,n,v*po(val[t],mod-2)%mod);//修改
val[t]=v;printf("%lld\n",lt.getv());//输出~
}return 0;//拜拜程序~
}
```