降幂大法 | OceanEye's Blog

@OceanEye8年前

05/19

16:03

BZOJ4869

OceanEye 撰写 BZOJ 暴力神技巧线段树降幂大法无回复

这道题是这样子的……一个区间求和一个区间加幂

之前刚刚学了降幂大法就是为了写这道题:-D

然后就直接肝……当然最后还要展开多一层的1~~[EXM?]~~

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

#define N 100010

int f[50],tmp;
int n,m,p,c;
int Arr[N],time[N];
bool b[N]; int pri[N],tot;

int calc_phi(int x)
{
	int ret=x;
	for(int i=0;pri[i]*pri[i]<=x&&i<tot;i++) if(x%pri[i]==0)
	{
		ret-=ret/pri[i];
		while(x%pri[i]==0) x/=pri[i];
	}
	if(x>1) ret-=(ret/x);
	return ret;
}

int ksm(int x,int top,int mod,bool &pp)
{
	int ret=1;
	bool ccc=false;
	for(;top;top>>=1)
	{
		if(top&1) pp|=ccc|(1LL*ret*x>=mod),ret=1LL*ret*x%mod;
		ccc=1LL*x*x>=mod;
		x=1LL*x*x%mod;
	}
	return ret;
}

int solve(int a,int L)
{
	bool pp=(a>=f[L]);
	int mmp=a%f[L];
	for(;L;L--) mmp=ksm(c,mmp+(pp?f[L]:0),f[L-1],pp);
	return mmp;
}

struct node
{
	int l,r,c[2],sum;
	bool is;
}pool[N<<2];

int pcnt;
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define L pool[x].l
#define R pool[x].r
#define SUM pool[x].sum
#define TIME time[L]
#define IS pool[x].is
inline void PushUP(int x)
{
	SUM = pool[Lc].sum+pool[Rc].sum;
	SUM>=p?SUM-=p:SUM;
	IS=pool[Lc].is&pool[Rc].is;
}

void build(int l,int r,int x)
{
	L=l; R=r;
	if(l==r)
	{
		SUM=Arr[l]%p;
		IS=(time[l]==tmp);
		return;
	}
	int mid = (l+r) >>1;
	build(l,mid,Lc=++pcnt);
	build(mid+1,r,Rc=++pcnt);
	PushUP(x);
}

void rebuild(const int &l,const int &r,int x)
{
	if(IS) return;
	if(L==R)
	{
		TIME++;
		SUM=solve(Arr[L],TIME);
		IS=(TIME==tmp);
		return;
	}
	int mid=(L+R)>>1;
	if(mid>=l) rebuild(l,r,Lc);
	if(mid <r) rebuild(l,r,Rc);
	PushUP(x);
}

int query(const int& l,const int& r,int x)
{
	if(l<=L&&R<=r) return pool[x].sum;
	if(R<l||L>r) return 0;
	int ret=0; int mid = (L+R)>>1;
	ret+=query(l,r,Lc);
	ret+=query(l,r,Rc);
	return ret>=p?ret-p:ret;
}

void pre()
{
	for(int i=1;i<=n;i++) read(Arr[i]);
	int x=p;
	for(int i=2;i*i<=p;i++)
	{
		!b[i]?pri[tot++]=i:b[i];
		for(int j=0;j<tot&&pri[j]*i<N;j++)
		{
			b[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
	while(x>1) f[tmp++]=x,x=calc_phi(x);
	f[tmp++]=1; f[tmp]=1;
	build(1,n,0);
}

int main()
{
	freopen("BZOJ4869.in","r",stdin);
	read(n); read(m); read(p); read(c);
	pre();
	static int a,l,r;
	while(m--)
	{
		read(a); read(l); read(r);
		if(a) printf("%d\n",query(l,r,0));
		else(rebuild(l,r,0));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

#include <cstdio>

#include <algorithm>

#include <cstring>

#define ll long long

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

int f[50],tmp;

int n,m,p,c;

int Arr[N],time[N];

bool b[N]; int pri[N],tot;

int calc_phi(int x)

{

int ret=x;

for(int i=0;pri[i]*pri[i]<=x&&i<tot;i++) if(x%pri[i]==0)

{

ret-=ret/pri[i];

while(x%pri[i]==0) x/=pri[i];

}

if(x>1) ret-=(ret/x);

return ret;

}

int ksm(int x,int top,int mod,bool &pp)

{

int ret=1;

bool ccc=false;

for(;top;top>>=1)

{

if(top&1) pp|=ccc|(1LL*ret*x>=mod),ret=1LL*ret*x%mod;

ccc=1LL*x*x>=mod;

x=1LL*x*x%mod;

}

return ret;

}

int solve(int a,int L)

{

bool pp=(a>=f[L]);

int mmp=a%f[L];

for(;L;L--) mmp=ksm(c,mmp+(pp?f[L]:0),f[L-1],pp);

return mmp;

}

struct node

{

int l,r,c[2],sum;

bool is;

}pool[N<<2];

int pcnt;

#define Lc pool[x].c[0]

#define Rc pool[x].c[1]

#define L pool[x].l

#define R pool[x].r

#define SUM pool[x].sum

#define TIME time[L]

#define IS pool[x].is

inline void PushUP(int x)

{

SUM = pool[Lc].sum+pool[Rc].sum;

SUM>=p?SUM-=p:SUM;

IS=pool[Lc].is&pool[Rc].is;

}

void build(int l,int r,int x)

{

L=l; R=r;

if(l==r)

{

SUM=Arr[l]%p;

IS=(time[l]==tmp);

return;

}

int mid = (l+r) >>1;

build(l,mid,Lc=++pcnt);

build(mid+1,r,Rc=++pcnt);

PushUP(x);

}

void rebuild(const int &l,const int &r,int x)

{

if(IS) return;

if(L==R)

{

TIME++;

SUM=solve(Arr[L],TIME);

IS=(TIME==tmp);

return;

}

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

if(mid>=l) rebuild(l,r,Lc);

if(mid <r) rebuild(l,r,Rc);

PushUP(x);

}

int query(const int& l,const int& r,int x)

{

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

if(R<l||L>r) return 0;

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

ret+=query(l,r,Lc);

ret+=query(l,r,Rc);

return ret>=p?ret-p:ret;

}

void pre()

{

for(int i=1;i<=n;i++) read(Arr[i]);

int x=p;

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

{

!b[i]?pri[tot++]=i:b[i];

for(int j=0;j<tot&&pri[j]*i<N;j++)

{

b[pri[j]*i]=1;

if(i%pri[j]==0) break;

}

while(x>1) f[tmp++]=x,x=calc_phi(x);

f[tmp++]=1; f[tmp]=1;

build(1,n,0);

}

int main()

{

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

read(n); read(m); read(p); read(c);

pre();

static int a,l,r;

while(m--)

{

read(a); read(l); read(r);

if(a) printf("%d\n",query(l,r,0));

else(rebuild(l,r,0));

}

return 0;

}

BZOJ4869

@OceanEye8年前

05/12

17:25

BZOJ3884

OceanEye 撰写欧拉函数降幂大法无回复

降幂大法:-D
安利Tangjz题解
出题人的题解也是很强的qwq

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <map>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

int k;
map<int,int> f;

int ksm(int x,int a,int mod)
{
	ll ret=1;
	for(;a;a>>=1)
	{
		if(a&1) ret=ret*x%mod;
		x=(ll)x*x%mod;
	}
	return (int)ret;
}

int calc_phi(int x)
{
	int ret=x;
	for(int i=2;i*i<=x;i++) if(x%i==0)
	{
		ret-=ret/i;
		while(x%i==0) x/=i;
	}
	if(x>1) ret-=ret/x;
	return ret;
}

int solve(int p)
{
	if(f.count(p)) return f[p];
	int phi=calc_phi(p);
	return f[p]=ksm(2,solve(phi)+phi,p);
}

int T;

int main()
{
	f[1]=0;
	for(read(T);T;T--) { read(k); printf("%d\n",solve(k)); }
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <map>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

int k;

map<int,int> f;

int ksm(int x,int a,int mod)

{

ll ret=1;

for(;a;a>>=1)

{

if(a&1) ret=ret*x%mod;

x=(ll)x*x%mod;

}

return (int)ret;

}

int calc_phi(int x)

{

int ret=x;

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

{

ret-=ret/i;

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

}

if(x>1) ret-=ret/x;

return ret;

}

int solve(int p)

{

if(f.count(p)) return f[p];

int phi=calc_phi(p);

return f[p]=ksm(2,solve(phi)+phi,p);

}

int T;

int main()

{

f[1]=0;

for(read(T);T;T--) { read(k); printf("%d\n",solve(k)); }

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye8年前

BZOJ4869

BZOJ4869

@OceanEye8年前

BZOJ3884

BZOJ3884

友情链接

近期文章

标签