BZOJ4597: [Shoi2016]随机序列

Description

你的面前有N个数排成一行。分别为A1, A2, … , An。你打算在每相邻的两个 Ai和 Ai+1 间都插入一个加号或者

减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太

简单了，所以你还打算支持一个修改操作，可以修改某个Ai 的值。你能够编写一个程序对每个修改都输出修改完

之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是

在最初的表达式上进行。

Input

第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。

接下来一行 n 个非负整数，依次表示a1,a2...an

在接下来 Q 行，其中第 ?? 行两个非负整数Ti 和Vi，表示要将 A_ti 修改为 Vi。其中 1 ≤ Ti ≤ N。

保证对于 1 ≤ J ≤ N, 1 ≤ i≤ Q，都有 Aj,Vi ≤ 10^4。

N,Q<=100000,本题仅有三组数据

Output

输出共 Q 行，其中第 i 行表示第 i 个询问之后所有可能表达式的和，对10^9 + 7 取模。

Sample Input

5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60

Sample Output

890543652
252923708
942282590
228728040
608998099

一颗赛艇，我是这么推的结论：

首先考虑暴力DP，设S[i]表示∏j<=i Aj。f[i]表示前i个数在之间随便插数的结果之和，不难得到f[i]=∑j<i (2*f[j]) + S[i]。

然后3*f[i]-S[i]=∑j<=i (2*f[j])

f[i+1]=∑j<=i (2*f[j]) + S[i+1]

=3*f[i] (-S[i]+S[i+1])

考虑每个S[i]-S[i-1]对f[n]的影响，则f[n]=∑(S[i]-S[i-1])*3^(n-i)。

裂项一下，则f[n]=2*∑(S[i]*3^(n-i-1))+S[n]。

然后就可以用线段树简单维护一下答案了。

然后又想了一下，发现答案可以这样理解：枚举第一串*号拓展到哪个位置，除了放了n-1个*号的情况，下一步放+和放-号的答案刚好抵消，所以对答案的贡献刚好是S[i]*3^(n-i-1)。

膜。的。长。者。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

typedef long long ll;

const int maxn=100010;

const int mod=1000000007;

ll pow(ll n,int m) {

	ll ans=1;

	for(;m;m>>=1,(n*=n)%=mod) if(m&1) (ans*=n)%=mod;

	return ans;

}

int n,q,A[maxn],xp[maxn];

ll pown,inv3,sumk[maxn<<2],sumv[maxn<<2];

void maintain(int o,int l,int r) {

	int mid=l+r>>1,lc=o<<1,rc=lc|1;

	sumk[o]=sumk[lc]*sumk[rc]%mod;

	sumv[o]=(sumv[lc]+sumv[rc]*xp[mid-l+1]%mod*sumk[lc])%mod;

}

void build(int o,int l,int r) {

	if(l==r) sumk[o]=A[l],sumv[o]=A[l]*pown%mod;

	else {

		int mid=l+r>>1,lc=o<<1,rc=lc|1;

		build(lc,l,mid);build(rc,mid+1,r);

		maintain(o,l,r);

	}

}

void update(int o,int l,int r,int p) {

	if(p==n) {A[n]=read();return;}

	if(l==r) sumk[o]=read(),sumv[o]=sumk[o]*pown%mod;

	else {

		int mid=l+r>>1,lc=o<<1,rc=lc|1;

		if(p<=mid) update(lc,l,mid,p);

		else update(rc,mid+1,r,p);

		maintain(o,l,r);

	}

}

int main() {

	n=read();q=read();xp[0]=1;inv3=pow(3,mod-2);pown=pow(3,n-2);

	rep(i,1,n) A[i]=read(),xp[i]=xp[i-1]*inv3%mod;

	build(1,1,n-1);

	rep(i,1,q) {

		update(1,1,n-1,read());

		printf("%lld\n",(sumv[1]*2+sumk[1]*A[n])%mod);

	}

	return 0;

}

秒客网