[BZOJ4869][六省联考2017]相逢是问候(线段树+扩展欧拉定理)

4869: [Shoi2017]相逢是问候

Time Limit: 40 Sec Memory Limit: 512 MB
Submit: 1313 Solved: 471
[Submit][Status][Discuss]

Description

Informatikverbindetdichundmich.

信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以

分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是

输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为

这个结果可能会很大，所以你只需要输出结果mod p的值即可。

Input

第一行有三个整数n,m,p,c，所有整数含义见问题描述。

接下来一行n个整数，表示a数组的初始值。

接下来m行，每行三个整数，其中第一个整数表示了操作的类型。

如果是0的话，表示这是一个修改操作，操作的参数为l,r。

如果是1的话，表示这是一个询问操作，操作的参数为l,r。

1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p

Output

对于每个询问操作，输出一行，包括一个整数表示答案mod p的值。

Sample Input

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

Sample Output

0
3

HINT

鸣谢多名网友提供正确数据，已重测！

Source

黑吉辽沪冀晋六省联考&&鸣谢xlk授权本OJ使用权

[Submit][Status][Discuss]

扩展欧拉定理：$a^x \equiv a^{x\% \phi (p)+[x> \phi (p)] \phi (p)} (mod p)$，a和p可以不互质。

我们可以不断展开：$c^{c^x} \equiv c^{c^x\% \phi (p)+\phi(p) } \equiv c^{c^{x\% \phi(\phi(p))+\phi(\phi(p))}\%\phi(p)+\phi(p)}(mod p)$，以此类推。

可以证明在$O(\log n)$次内模数会变为1，也就是最后会变成$x\%1+1$所以这个直接用线段树维护就好，如果一个区间内的所有数都变成1了就不必处理。

注意最后要加一个$\phi(1)$：https://blog.csdn.net/llgyc/article/details/71076172

#include<cstdio>

#include<algorithm>

#define ls (x<<1)

#define rs (x<<1)|1

#define lson ls,L,mid

#define rson rs,mid+1,R

#define rep(i,l,r) for (int i=l; i<=r; i++)

typedef long long ll;

using namespace std;

const int N=100010;

int n,m,op,l,r,a[N],cnt,c,dep[N<<2];

ll sum[N<<2],mod[N];

ll phi(ll x){

	ll res=x;

	for (int i=2; i*i<=x; i++)

		if (!(x%i)){

			res=res*(i-1)/i;

			while (!(x%i)) x/=i;

		}

	if (x>1) res=res*(x-1)/x;

	return res;

}

ll pow(ll a,ll b,ll p,bool &f){

	ll res=1; f=0;

	while (b){

		if (b & 1) f|=(res*a>=p),res=(res*a)%p;

		f|=(a*a>=p && b>1); a=(a*a)%p; b>>=1;

	}

	return res;

}

ll calc(ll x,ll p){

	ll res=x; bool f;

	if (res>=mod[p]) res=res%mod[p]+mod[p];

	while (p--){

		res=pow(c,res,mod[p],f);

		if (f) res+=mod[p];

	}

	return res%mod[0];

}

void build(int x,int L,int R){

	if (L==R) { dep[x]=0; sum[x]=a[L]; return; }

	int mid=(L+R)>>1;

	build(ls,L,mid); build(rs,mid+1,R);

	sum[x]=(sum[ls]+sum[rs])%mod[0];

}

void mdf(int x,int L,int R,int l,int r){

	if (dep[x]>=cnt) return;

	if (L==R){ sum[x]=calc(a[L],++dep[x]); return; }

	int mid=(L+R)>>1;

	if (r<=mid) mdf(lson,l,r);

	else if (l>mid) mdf(rson,l,r);

		else mdf(lson,l,mid),mdf(rson,mid+1,r);

	dep[x]=min(dep[ls],dep[rs]); sum[x]=(sum[ls]+sum[rs])%mod[0];

}

ll que(int x,int L,int R,int l,int r){

	if (L==l && r==R) return sum[x];

	int mid=(L+R)>>1;

	if (r<=mid) return que(lson,l,r);

	else if (l>mid) return que(rson,l,r);

		else return (que(lson,l,mid)+que(rson,mid+1,r))%mod[0];

}

int main(){

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

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

	scanf("%d%d%lld%d",&n,&m,&mod[0],&c);

	while (mod[cnt]!=1) cnt++,mod[cnt]=phi(mod[cnt-1]);

	mod[++cnt]=1;

	rep(i,1,n) scanf("%d",&a[i]);

	build(1,1,n);

	while (m--){

		scanf("%d%d%d",&op,&l,&r);

		if (!op) mdf(1,1,n,l,r); else printf("%lld\n",que(1,1,n,l,r));

	}

	return 0;

}

巴特西

[BZOJ4869][六省联考2017]相逢是问候(线段树+扩展欧拉定理)

4869: [Shoi2017]相逢是问候

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章