相逢是問候

2017-09-09

---

Description

Informatik verbindet dich und mich. 信息將你我連結。(s:看到這個就感覺有毒 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 1 40 19910626 2 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 in_put 1 2 4 16 65536 114181021832559013700558137005581370055813700558137005581370055813700558137005581370055813700558137005581370055813700558 out_put

---

考試時這個題感覺好神奇..當時某個學長講的時候一臉mengbier,整個人都noip了..什么是φ?

歐拉函數裸題,一個數c在mod一個數的時候,在最多log₂p次會不變....

所以線段樹維護區間和,區間修改最小值;

修改時遍歷到每一個節點,暴力修改每一個改變的值,因為到一定的次數不會變,所以記錄一個tag代表這個區間一共修改了多少次...

當l==r時就是那個點修改次數...最多log₂p次就不用改了,時間復雜度n*2log(n)。記住,歐拉不要亂mod,會出事的...

#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll (long long) #define LL long long #define IN int using namespace std; const IN maxn=50000+99; const IN N=10000+99; int read(){int an=0,f=1;char ch=getchar();while(!('0'<=ch&&ch<='9')){if(ch=='-')f=-f;ch=getchar();}while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}return an*f; } IN phi[35],a[maxn],F; IN n,m,p,c; IN prime[maxn],isp[maxn],k,maxp;//k是質數個數,ips說明這是和數 struct saber{ IN sum,tag,l,r; }tr[maxn<<2]; IN Phi(IN x){LL ans=x;for(IN i=1;i<=k && prime[i]*prime[i]<=x;i++){if(!(x%prime[i]))ans=ans*(prime[i]-1)/prime[i];while(!(x%prime[i]))x=x/prime[i];}if(x>1)ans=ans/x*(x-1);return ans; } void euler(){for(IN i=2;i<=N;i++){if(!isp[i])k++,prime[k]=i;for(IN j=1;j<=k;j++){if(i*prime[j]>N)break;isp[i*prime[j]]=1;if(!(i%prime[j]))break;}}phi[maxp]=p;while(phi[maxp]!=1)maxp++,phi[maxp]=Phi(phi[maxp-1]);maxp++;phi[maxp]=1; } void build(IN k,IN l,IN r){tr[k].l=l;tr[k].r=r;if(l==r){tr[k].sum=a[l];return ;}IN mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } IN ask(IN k,IN i,IN j){IN l=tr[k].l,r=tr[k].r;if(l==i&&r==j)return tr[k].sum;IN mid=(l+r)>>1;if(mid>=j)return ask(k<<1,i,j);else if(i>mid)return ask(k<<1|1,i,j);else return (ask(k<<1,i,mid)+ask(k<<1|1,mid+1,j))%p; } IN qw(LL k,IN mod){LL ans=1;LL s=c;while(k){if(k&1)ans*=s;k>>=1;s*=s;if(s>=mod)F=1,s%=mod;if(ans>=mod)F=1,ans%=mod;}return ans%mod; } LL work(LL a,LL t){LL tmp=a;if(tmp>phi[t])tmp=tmp%phi[t]+phi[t];for(IN i=t;i>0;i--){F=0;tmp=qw(tmp,phi[i-1]);if(F)tmp+=phi[i-1],F=0;}return tmp; } void change(IN k,IN i,IN j){if(tr[k].tag>=maxp)return;LL l=tr[k].l,r=tr[k].r;if(l==r){tr[k].tag++;tr[k].sum=work(a[l],tr[k].tag)%p;return;}IN mid=(l+r)>>1;if(mid>=j)change(k<<1,i,j);else if(i>mid)change(k<<1|1,i,j);else {change(k<<1,i,mid);change(k<<1|1,mid+1,j);}tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;tr[k].tag=min(tr[k<<1].tag,tr[k<<1|1].tag); } int main(){n=read();m=read();p=read();c=read();for(IN i=1;i<=n;i++)a[i]=read();euler();build(1,1,n);while(m){m--;IN x,y,z;x=read();y=read();z=read();if(x){printf("%lld\n",ask(1,y,z)%p);}else {change(1,y,z);}}return 0; } 相逢是問候

by:s_a_b_e_r

---

表示考試結束學長講題的時候一臉memgbier+1

歐拉定理+線段樹維護

求c^cc……a[i]?%p的值

看上去一臉不可做，這要乘多少次

然而這個世界上存在著一個神奇的定理——歐拉定理EXT

a^x?≡a^{x%φ(m)+φ(m)}(mod m)

既然我們要求c^cx(mod p)

不妨設d=c^x?于是我們要求的就變成了c^d

據歐拉定理有c^d=c^{d%φ(p)+φ(p)}(mod p)

即c^cx=c^{cx%φ(p)+φ(p)}(mod p)

看不清？放大一下

c^cx=c^{cx%φ(p)+φ(p)}(mod p)

標記的部分是不是很眼熟？

這部分又滿足了歐拉定理

于是再抽一次φ變成

c^{cx%φ(φ(p))+φ(φ(p))%φ(p)+φ(p)}(mod p)

這樣一直抽下去，最后要%的東西會變成φ(φ(φ(φ(……p)))) (特別多個φ)

特別玄學的是這東西被φ多了就會變成1（據說最多log(p)次？）

然后就會出現x%1+1 = 0+1 = 1的狀況

然后再對它修改就沒什么用了，可以無視了

于是一發線段樹維護每個點被修改了多少次

以及涉及歐拉的部分都不要亂%p，包括快速冪，容易出事qwq

?

#include<iostream> #include<cstdio> #define ll long long using namespace std; const int N=50099,SP=10099; int pri[N],cp,phi[50],ci; bool isp[N],f; int n,m,p,c,a[N]; struct tree{ int l,r,tag; ll sum; }t[N<<2]; void update(int k){t[k].sum=t[k<<1].sum+t[k<<1|1].sum;t[k].tag=min(t[k<<1].tag,t[k<<1|1].tag); } void build(int k,int l,int r){t[k].l=l,t[k].r=r;if(l==r){t[k].sum=a[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);update(k); } int Phi(int x){//求歐拉函數int ans=x;for(int i=1;i<=cp&&pri[i]*pri[i]<=x;++i){if(!(x%pri[i]))ans=ans/pri[i]*(pri[i]-1);while(!(x%pri[i]))x/=pri[i];}if(x>1)ans=ans/x*(x-1);return ans; } void prime(){//歐拉篩素數for(int i=2;i<=SP;++i){if(!isp[i])pri[++cp]=i;for(int j=1;j<=cp;++j){if(i*pri[j]>N)break;isp[i*pri[j]]=1;if(i%pri[j]==0)break;}}phi[ci]=p;while(phi[ci]!=1)phi[++ci]=Phi(phi[ci-1]);phi[++ci]=1; } int kp(int x,int k,int mod){int ans=1;while(k){if(k&1){if(1ll*ans*x>=mod)f=1;ans=1ll*ans*x%mod;}if(1ll*x*x>=mod)f=1;x=1ll*x*x%mod;k>>=1;}return ans; } int C(int a,int x){//抽φ int tmp=a;if(tmp>phi[x])tmp=tmp%phi[x]+phi[x];//歐拉定理前提條件 for(int i=x;i>0;--i){f=0;tmp=kp(c,tmp,phi[i-1]);if(f==1)tmp+=phi[i-1];}return tmp; } void change(int k,int L,int R){if(t[k].tag>=ci)return;int l=t[k].l,r=t[k].r;if(l==r){t[k].sum=C(a[l],++t[k].tag);return;}int mid=(l+r)>>1;if(L<=mid)change(k<<1,L,R);if(R>mid)change(k<<1|1,L,R);update(k); } ll query(int k,int L,int R){int l=t[k].l,r=t[k].r;if(L<=l&&R>=r)return t[k].sum%p;if(r<L||l>R)return 0;return (query(k<<1,L,R)+query(k<<1|1,L,R))%p; } int main() {scanf("%d%d%d%d",&n,&m,&p,&c);for(int i=1;i<=n;++i)scanf("%d",&a[i]);build(1,1,n);prime();for(int i=1;i<=m;++i){int type,l,r;scanf("%d%d%d",&type,&l,&r);if(!type)change(1,l,r);else printf("%lld\n",query(1,l,r)%p);}return 0; } verbinden

?

by:wypx

---

?s:省選后聽見有人說誰mo誰是真***,今天我就在ans膜了個p,╮(╯▽╰)╭

w:這說明了什么（笑）

?

s:%數學dalao

w:果然數學題還是要放⑨啊w

轉載于:https://www.cnblogs.com/ck666/p/7499209.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[bzoj 4869] [六省联考2017] 相逢是问候的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。