BZOJ | OceanEye's Blog

BZOJ1031 [JSOI2007]字符加密Cipher

OceanEye 撰写 BZOJ 后缀数组字符串无回复

嗯这题不是权限题很友好
SA裸题
Read More →

BZOJ1031 [JSOI2007]字符加密Cipher

BZOJ3329

OceanEye 撰写 BZOJ 数位DP 矩阵快速幂无回复

12ms卡进前二十也是很人品……

第一问是二进制下的数位DP
第二问是个斐波那契数列……

然后分开来写一写就好了
【差点不会写矩阵乘法系列】

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#define ll long long

#define For(i,a,b) for(int i=a;i<=b;++i)

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

//dp[wei][is upper ?][0/1]
//dp[i][0][1] ->  dp[i-1][0][0]
//dp[i][0][0] -> dp[i-1][0][0] + dp[i-1][0][1]
//dp[i][1][1] -> dp[i-1][0][0] + dp[i-1][
//dp[i][1][1] -> dp[i-1][1][0]
ll dp[70][2][2];
ll dfs(int a,int b,int c,const ll &d)
{
	if(dp[a][b][c]) return dp[a][b][c];
	if(a==0) return 1;
#define p (d&(1LL<<(a-1)))
	if(!b) return dp[a][b][c]= (c==0?(dfs(a-1,0,1,d)+dfs(a-1,0,0,d)):dfs(a-1,0,0,d)) ;
	else
	{
		if(c) return p?dfs(a-1,0,0,d):dfs(a-1,1,0,d);
		else return p?dfs(a-1,0,0,d)+dfs(a-1,1,1,d):dfs(a-1,1,0,d);
	}
#undef p
}

const int sqr[2][2]={{0,1},{1,1}};

int ksm(ll T)
{
//	puts("SB");
#define mod 1000000007LL
	static ll a[2][2],b[2][2],c[2],ans[2];
	a[0][0]=sqr[0][0]; a[0][1]=sqr[0][1]; a[1][0]=sqr[1][0]; a[1][1]=sqr[1][1];
	ans[0]=0; ans[1]=1;
	for(;T;T>>=1)
	{
		if(T&1)
		{
			c[0]=ans[0]*a[0][0]+ans[1]*a[0][1];
			c[1]=ans[0]*a[1][0]+ans[1]*a[1][1];
			ans[0]=c[0]%mod; ans[1]=c[1]%mod;
		}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				b[i][j]=0;
				for(int k=0;k<2;k++) b[i][j]+=a[i][k]*a[k][j];
			}
		a[0][1]=b[0][1]%mod; a[0][0]=b[0][0]%mod; a[1][0]=b[1][0]%mod; a[1][1]=b[1][1]%mod;
	}
	return (int)ans[0];
}

void Main()
{
	static int t; static ll n;
	read(n); t=0; for(ll i=1;i<=n;i<<=1,t++);
	printf("%lld\n%d\n",dfs(t,1,0,n)-1,ksm(n+2));
}

int main()
{
	int T;

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <cmath>

#define ll long long

#define For(i,a,b) for(int i=a;i<=b;++i)

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

char cc; int C;

template <class T>

void read( T &x )

{

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

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

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

x*=C;

}

#undef p

using namespace std;

//dp[wei][is upper ?][0/1]

//dp[i][0][1] -> dp[i-1][0][0]

//dp[i][0][0] -> dp[i-1][0][0] + dp[i-1][0][1]

//dp[i][1][1] -> dp[i-1][0][0] + dp[i-1][

//dp[i][1][1] -> dp[i-1][1][0]

ll dp[70][2][2];

ll dfs(int a,int b,int c,const ll &d)

{

if(dp[a][b][c]) return dp[a][b][c];

if(a==0) return 1;

#define p (d&(1LL<<(a-1)))

if(!b) return dp[a][b][c]= (c==0?(dfs(a-1,0,1,d)+dfs(a-1,0,0,d)):dfs(a-1,0,0,d)) ;

else

{

if(c) return p?dfs(a-1,0,0,d):dfs(a-1,1,0,d);

else return p?dfs(a-1,0,0,d)+dfs(a-1,1,1,d):dfs(a-1,1,0,d);

}

#undef p

}

const int sqr[2][2]={{0,1},{1,1}};

int ksm(ll T)

{

// puts("SB");

#define mod 1000000007LL

static ll a[2][2],b[2][2],c[2],ans[2];

a[0][0]=sqr[0][0]; a[0][1]=sqr[0][1]; a[1][0]=sqr[1][0]; a[1][1]=sqr[1][1];

ans[0]=0; ans[1]=1;

for(;T;T>>=1)

{

if(T&1)

{

c[0]=ans[0]*a[0][0]+ans[1]*a[0][1];

c[1]=ans[0]*a[1][0]+ans[1]*a[1][1];

ans[0]=c[0]%mod; ans[1]=c[1]%mod;

}

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

{

b[i][j]=0;

for(int k=0;k<2;k++) b[i][j]+=a[i][k]*a[k][j];

}

a[0][1]=b[0][1]%mod; a[0][0]=b[0][0]%mod; a[1][0]=b[1][0]%mod; a[1][1]=b[1][1]%mod;

}

return (int)ans[0];

}

void Main()

{

static int t; static ll n;

read(n); t=0; for(ll i=1;i<=n;i<<=1,t++);

printf("%lld\n%d\n",dfs(t,1,0,n)-1,ksm(n+2));

}

int main()

{

int T;

BZOJ3329

BZOJ2243

OceanEye 撰写 BZOJ 树树链剖分线段树无回复

树链剖分
细节打错了然后wa了好久

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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 to[N<<2],nxt[N<<2],fst[N],e_tot;
void add_e(const int &_,const int &__)
{
	to[e_tot]=__; nxt[e_tot]=fst[_]++; fst[_]=e_tot++;
	to[e_tot]=_; nxt[e_tot]=fst[__]++; fst[__]=e_tot++;
}
struct node
{
	int l,r,c[2];
	int cnt,col[2];
	int tag;
	node() { tag=-1; }
}pool[N<<2];
int pcnt=1;
#define L pool[x].l
#define R pool[x].r
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define Lcol pool[x].col[0]
#define Rcol pool[x].col[1]
#define CNT pool[x].cnt
#define TAG pool[x].tag
void PushUP(int x)
{
	CNT=pool[Lc].cnt+pool[Rc].cnt-(int)(pool[Lc].col[1]==pool[Rc].col[0]);
	Lcol=pool[Lc].col[0];
	Rcol=pool[Rc].col[1];
	if(CNT==1) TAG=Lcol;
}
void PushDown(int x)
{
	pool[Lc].col[0]=pool[Lc].col[1]=pool[Rc].col[0]=pool[Rc].col[1]=pool[Lc].tag=pool[Rc].tag=TAG;
	pool[Lc].cnt=pool[Rc].cnt=1;
	TAG=-1;
}

void build(int x,int l,int r,int a[])
{
	L=l; R=r;
	if(l==r)
	{
		Lcol=Rcol=a[l];
		CNT=1;
		return;
	}
	int mid=(l+r)>>1;
	build(Lc=++pcnt,l,mid,a);
	build(Rc=++pcnt,mid+1,r,a);
	PushUP(x);
}

int query(int x,int l,int r)
{
	if(~TAG) return 1;
	if(l<=L&&R<=r) return CNT;
	int mid=(L+R)>>1;
	if(mid>=r) return query(Lc,l,r);
	if(mid<l) return query(Rc,l,r);
	return query(Lc,l,r)+query(Rc,l,r)-(int)(pool[Lc].col[1]==pool[Rc].col[0]);
}

int fill(int x,int l,int r,int col)
{
	if(l<=L&&R<=r)
	{
		Lcol=Rcol=TAG=col; CNT=1;
		return 0;
	}
	int mid=(L+R)>>1;
	if(~TAG) PushDown(x);
	if(mid>=l) fill(Lc,l,r,col);
	if(mid<r) fill(Rc,l,r,col);
	PushUP(x);
}

int find(int x,int pos)
{
	if(L==R) return Lcol; 
	if(~TAG) return TAG;
	return find(pos<=((L+R)>>1)?Lc:Rc,pos);
}
int col[N],a[N],id[N],up[N],fa[N],dep[N],mxson[N],siz[N],tot;
int n,m;
void dfs1(int x,int f)
{
	siz[x]=1;
	for(int i=fst[x];~i;i=nxt[i])
	{
		if(to[i]==f) continue;
		dfs1(to[i],x);
		if(siz[to[i]]>siz[mxson[x]]) mxson[x]=to[i];
		siz[x]+=siz[to[i]];
	}
}

void dfs2(int x,int f)
{
	id[x]=++tot;
	if(!mxson[x]) return;
	fa[mxson[x]]=fa[x]; up[mxson[x]]=up[x]; dep[mxson[x]]=dep[x];
	dfs2(mxson[x],x);
	for(int i=fst[x];~i;i=nxt[i])
	{
		if(to[i]==mxson[x]||to[i]==f) continue;
		fa[to[i]]=x; up[to[i]]=to[i]; dep[to[i]]=dep[x]+1;
		dfs2(to[i],x);
	}
}

void init()
{
	memset(fst,-1,sizeof(fst));
	int _,__;
	read(n); read(m);
	For(i,1,n) read(col[i]);
	For(i,1,n-1)
	{
		read(_); read(__);
		add_e(_,__);
	}
	dfs1(1,0);
	up[1]=1;
	dfs2(1,0);
	for(int i=1;i<=n;i++) a[id[i]]=col[i];
	build(pcnt,1,n,a);
}

int LCA(int x,int y)
{
	if(dep[x]>dep[y]) swap(x,y);
	while(dep[x]<dep[y]) y=fa[y];
	while(up[x]!=up[y]) x=fa[x],y=fa[y];
	return id[x]>id[y]?y:x;
}

int find_col(int pos)
{ return find(1,pos); }

int solve()
{
	static int rt,ret,a,b,last_a,last_b;
	read(a); read(b); rt=LCA(a,b);
	ret=last_a=last_b=0;
	while(id[a]>=id[rt])
	{
		ret+=query(1,max(id[up[a]],id[rt]),id[a]);
		if(last_a) ret-=(int)(find_col(id[last_a])==find_col(id[a]));
		last_a=up[a]; a=fa[a];
	}
	while(id[b]>=id[rt])
	{
		ret+=query(1,max(id[up[b]],id[rt]),id[b]);
		if(last_b) ret-=(int)(find_col(id[last_b])==find_col(id[b]));
		last_b=up[b]; b=fa[b];
	}
	return ret-1;
}

void fill()
{
	static int rt,a,b,col;
	read(a); read(b); read(col); rt=LCA(a,b);
	while(id[a]>=id[rt])
	{
		fill(1,max(id[up[a]],id[rt]),id[a],col);
		a=fa[a];
	}
	while(id[b]>=id[rt])
	{
		fill(1,max(id[up[b]],id[rt]),id[b],col);
		b=fa[b];
	}
}

int main()
{
	freopen("BZOJ2243.in","r",stdin);
	char s[10];
	init();
	while(m--)
	{
		scanf("%s",s);
		if(s[0]=='Q') printf("%d\n",solve());
		else fill();
	}
	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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

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

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

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 to[N<<2],nxt[N<<2],fst[N],e_tot;

void add_e(const int &_,const int &__)

{

to[e_tot]=__; nxt[e_tot]=fst[_]++; fst[_]=e_tot++;

to[e_tot]=_; nxt[e_tot]=fst[__]++; fst[__]=e_tot++;

}

struct node

{

int l,r,c[2];

int cnt,col[2];

int tag;

node() { tag=-1; }

}pool[N<<2];

int pcnt=1;

#define L pool[x].l

#define R pool[x].r

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

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

#define Lcol pool[x].col[0]

#define Rcol pool[x].col[1]

#define CNT pool[x].cnt

#define TAG pool[x].tag

void PushUP(int x)

{

CNT=pool[Lc].cnt+pool[Rc].cnt-(int)(pool[Lc].col[1]==pool[Rc].col[0]);

Lcol=pool[Lc].col[0];

Rcol=pool[Rc].col[1];

if(CNT==1) TAG=Lcol;

}

void PushDown(int x)

{

pool[Lc].col[0]=pool[Lc].col[1]=pool[Rc].col[0]=pool[Rc].col[1]=pool[Lc].tag=pool[Rc].tag=TAG;

pool[Lc].cnt=pool[Rc].cnt=1;

TAG=-1;

}

void build(int x,int l,int r,int a[])

{

L=l; R=r;

if(l==r)

{

Lcol=Rcol=a[l];

CNT=1;

return;

}

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

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

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

PushUP(x);

}

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

{

if(~TAG) return 1;

if(l<=L&&R<=r) return CNT;

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

if(mid>=r) return query(Lc,l,r);

if(mid<l) return query(Rc,l,r);

return query(Lc,l,r)+query(Rc,l,r)-(int)(pool[Lc].col[1]==pool[Rc].col[0]);

}

int fill(int x,int l,int r,int col)

{

if(l<=L&&R<=r)

{

Lcol=Rcol=TAG=col; CNT=1;

return 0;

}

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

if(~TAG) PushDown(x);

if(mid>=l) fill(Lc,l,r,col);

if(mid<r) fill(Rc,l,r,col);

PushUP(x);

}

int find(int x,int pos)

{

if(L==R) return Lcol;

if(~TAG) return TAG;

return find(pos<=((L+R)>>1)?Lc:Rc,pos);

}

int col[N],a[N],id[N],up[N],fa[N],dep[N],mxson[N],siz[N],tot;

int n,m;

void dfs1(int x,int f)

{

siz[x]=1;

for(int i=fst[x];~i;i=nxt[i])

{

if(to[i]==f) continue;

dfs1(to[i],x);

if(siz[to[i]]>siz[mxson[x]]) mxson[x]=to[i];

siz[x]+=siz[to[i]];

}

void dfs2(int x,int f)

{

id[x]=++tot;

if(!mxson[x]) return;

fa[mxson[x]]=fa[x]; up[mxson[x]]=up[x]; dep[mxson[x]]=dep[x];

dfs2(mxson[x],x);

for(int i=fst[x];~i;i=nxt[i])

{

if(to[i]==mxson[x]||to[i]==f) continue;

fa[to[i]]=x; up[to[i]]=to[i]; dep[to[i]]=dep[x]+1;

dfs2(to[i],x);

}

void init()

{

memset(fst,-1,sizeof(fst));

int _,__;

read(n); read(m);

For(i,1,n) read(col[i]);

For(i,1,n-1)

{

read(_); read(__);

add_e(_,__);

}

dfs1(1,0);

up[1]=1;

dfs2(1,0);

for(int i=1;i<=n;i++) a[id[i]]=col[i];

build(pcnt,1,n,a);

}

int LCA(int x,int y)

{

if(dep[x]>dep[y]) swap(x,y);

while(dep[x]<dep[y]) y=fa[y];

while(up[x]!=up[y]) x=fa[x],y=fa[y];

return id[x]>id[y]?y:x;

}

int find_col(int pos)

{ return find(1,pos); }

int solve()

{

static int rt,ret,a,b,last_a,last_b;

read(a); read(b); rt=LCA(a,b);

ret=last_a=last_b=0;

while(id[a]>=id[rt])

{

ret+=query(1,max(id[up[a]],id[rt]),id[a]);

if(last_a) ret-=(int)(find_col(id[last_a])==find_col(id[a]));

last_a=up[a]; a=fa[a];

}

while(id[b]>=id[rt])

{

ret+=query(1,max(id[up[b]],id[rt]),id[b]);

if(last_b) ret-=(int)(find_col(id[last_b])==find_col(id[b]));

last_b=up[b]; b=fa[b];

}

return ret-1;

}

void fill()

{

static int rt,a,b,col;

read(a); read(b); read(col); rt=LCA(a,b);

while(id[a]>=id[rt])

{

fill(1,max(id[up[a]],id[rt]),id[a],col);

a=fa[a];

}

while(id[b]>=id[rt])

{

fill(1,max(id[up[b]],id[rt]),id[b],col);

b=fa[b];

}

int main()

{

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

char s[10];

init();

while(m--)

{

scanf("%s",s);

if(s[0]=='Q') printf("%d\n",solve());

else fill();

}

return 0;

}

数据

7 8
1 1 1 1 1 1 1
1 2
2 3
3 4
2 5
1 6
5 7
Q 3 5
Q 3 7
C 1 4 2
Q 3 5
Q 3 7
C 3 6 2
Q 3 5
Q 3 7

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

7 8

1 1 1 1 1 1 1

1 2

2 3

3 4

2 5

1 6

5 7

Q 3 5

Q 3 7

C 1 4 2

Q 3 5

Q 3 7

C 3 6 2

Q 3 5

Q 3 7

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

BZOJ2243

Description

XWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。
XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。
称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作（可以是上取整或者下取整），使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

Input

第一行一个整数N,N ≤ 100。
接下来N行每行包含N个绝对值小于等于1000的实数，最多一位小数。

Output

输出一行，即取整后A矩阵的元素之和的最大值。无解输出No。

Sample Input

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

Sample Output

129

HINT

【数据规模与约定】

有10组数据，n的大小分别为10,20,30…100。

【样例说明】

样例中取整后满足XWW性的和最大的矩阵为：

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

朴素的建图，只是跑的网络流模式变了

然后就可以随便艹了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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 EE 80000
#define N 300
#define source 0
#define sink N-1
#define source_ N-2
#define sink_ N-3
struct Tedge
{
	int to,flow;
}edge[EE];
int e_tot,nxt[EE],fst[N];
#define E edge[i]
#define FLOW E.flow
#define TO E.to
#define NXT nxt[i]
#define calc(i) (n+i)
void add_e(int from,int to,int flow)
{
	static int &i=e_tot;
	TO=to; FLOW=flow; NXT=fst[from]; fst[from]=i++;
	TO=from; FLOW=0; NXT=fst[to]; fst[to]=i++;
}

double a[N][N];
int imp[N],in[N];
int n,S,T;
void init()
{
	int _;
	memset(fst,-1,sizeof(fst));
	read(n);
	For(i,1,n)
		for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]);
	For(i,1,n-1)
		for(int j=1;j<n;j++)
		{
			_=(int)floor(a[i][j]);
			if(ceil(a[i][j])!=_) add_e(i,calc(j),1);
			in[i]-=_; in[calc(j)]+=_;
		}
	For(i,1,n-1)
	{
		_=floor(a[i][n]);
		in[i]+=_;
		in[source]-=_;
		if(ceil(a[i][n])!=_) add_e(source,i,1);
	}
	For(i,1,n-1)
	{
		_=floor(a[n][i]);
		in[sink]+=_;
		in[calc(i)]-=_;
		if(ceil(a[n][i])!=_) add_e(calc(i),sink,1);
	}
	add_e(sink,source,INF);
	For(i,0,N-1) if(in[i]) 
	{
		in[i]>0?add_e(source_,i,in[i]):add_e(i,sink_,-in[i]);
		imp[i]=e_tot-2;
	}
}
int cnt[N],d[N];
bool bfs()
{
	memset(d,0,sizeof(d));
	memset(cnt,0,sizeof(cnt));
	static int queue[65540],x;
	static unsigned short int he=0,ta=0;
	queue[++he]=T;
	d[T]=1;
	while(he!=ta)
	{
		x=queue[++ta]; cnt[d[x]]++;
		for(int i=fst[x];~i;i=NXT) if(!d[TO]&&edge[i^1].flow)
		{ d[TO]=d[x]+1; queue[++he]=TO; }
	}
	return d[S];
}
void cp(int &x,int y) { x>y?x=y:x; }
int p[N];

int Augment()
{
	static int node,c,i;
	node=T; c=INF;
	while(node!=S)
	{
		i=p[node]; cp(c,FLOW);
		node=edge[i^1].to;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c;
		i^=1; FLOW+=c;
		node=TO;
	}
	return c;
}

int ISAP()
{
	static int node,cur[N],ret;
	static bool flag;
	if(!bfs()) return 0;
	node=S; ret=0;
	for(int i=0;i<N;i++) cur[i]=fst[i];
	while(d[S]<n*2+5)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(int i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)
		{
			p[TO]=i;
			cur[node]=i;
			node=TO;
			flag=true;
			break;
		}
		if(flag) continue;
		int M=N-1;
		if(!--cnt[d[node]]) break;
		for(int i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1);
		cnt[d[node]=M]++;
		cur[node]=fst[node];
		node==S?node:node=edge[p[node]^1].to;
	}
	return ret;
}

bool check()
{
	For(i,0,N-1) if(imp[i]) if(edge[imp[i]].flow) return false;
	return true;
}

int main()
{
	init();
	S=source_,T=sink_;
	ISAP();
//	printf("%d\n",ISAP());
	if(!check())
	{
		puts("-1");
		return 0;
	}
	S=source,T=sink;
	printf("%d\n",ISAP()*3);
	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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#define ll long long

#define INF 1000000000

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

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

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 EE 80000

#define N 300

#define source 0

#define sink N-1

#define source_ N-2

#define sink_ N-3

struct Tedge

{

int to,flow;

}edge[EE];

int e_tot,nxt[EE],fst[N];

#define E edge[i]

#define FLOW E.flow

#define TO E.to

#define NXT nxt[i]

#define calc(i) (n+i)

void add_e(int from,int to,int flow)

{

static int &i=e_tot;

TO=to; FLOW=flow; NXT=fst[from]; fst[from]=i++;

TO=from; FLOW=0; NXT=fst[to]; fst[to]=i++;

}

double a[N][N];

int imp[N],in[N];

int n,S,T;

void init()

{

int _;

memset(fst,-1,sizeof(fst));

read(n);

For(i,1,n)

for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]);

For(i,1,n-1)

for(int j=1;j<n;j++)

{

_=(int)floor(a[i][j]);

if(ceil(a[i][j])!=_) add_e(i,calc(j),1);

in[i]-=_; in[calc(j)]+=_;

}

For(i,1,n-1)

{

_=floor(a[i][n]);

in[i]+=_;

in[source]-=_;

if(ceil(a[i][n])!=_) add_e(source,i,1);

}

For(i,1,n-1)

{

_=floor(a[n][i]);

in[sink]+=_;

in[calc(i)]-=_;

if(ceil(a[n][i])!=_) add_e(calc(i),sink,1);

}

add_e(sink,source,INF);

For(i,0,N-1) if(in[i])

{

in[i]>0?add_e(source_,i,in[i]):add_e(i,sink_,-in[i]);

imp[i]=e_tot-2;

}

int cnt[N],d[N];

bool bfs()

{

memset(d,0,sizeof(d));

memset(cnt,0,sizeof(cnt));

static int queue[65540],x;

static unsigned short int he=0,ta=0;

queue[++he]=T;

d[T]=1;

while(he!=ta)

{

x=queue[++ta]; cnt[d[x]]++;

for(int i=fst[x];~i;i=NXT) if(!d[TO]&&edge[i^1].flow)

{ d[TO]=d[x]+1; queue[++he]=TO; }

}

return d[S];

}

void cp(int &x,int y) { x>y?x=y:x; }

int p[N];

int Augment()

{

static int node,c,i;

node=T; c=INF;

while(node!=S)

{

i=p[node]; cp(c,FLOW);

node=edge[i^1].to;

}

node=T;

while(node!=S)

{

i=p[node]; FLOW-=c;

i^=1; FLOW+=c;

node=TO;

}

return c;

}

int ISAP()

{

static int node,cur[N],ret;

static bool flag;

if(!bfs()) return 0;

node=S; ret=0;

for(int i=0;i<N;i++) cur[i]=fst[i];

while(d[S]<n*2+5)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

for(int i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)

{

p[TO]=i;

cur[node]=i;

node=TO;

flag=true;

break;

}

if(flag) continue;

int M=N-1;

if(!--cnt[d[node]]) break;

for(int i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1);

cnt[d[node]=M]++;

cur[node]=fst[node];

node==S?node:node=edge[p[node]^1].to;

}

return ret;

}

bool check()

{

For(i,0,N-1) if(imp[i]) if(edge[imp[i]].flow) return false;

return true;

}

int main()

{

init();

S=source_,T=sink_;

ISAP();

// printf("%d\n",ISAP());

if(!check())

{

puts("-1");

return 0;

}

S=source,T=sink;

printf("%d\n",ISAP()*3);

return 0;

}

BZOJ3698

@OceanEye7年前

05/29

21:46

BZOJ1079

OceanEye 撰写 BZOJ DP 无回复

dp[a][b][c][d][e][pre] = dp[a-1][b][c][d][e][1]*系数 + … + dp[a][b][c][d][e-1][5]*系数

其中a, b, c, d, e是能涂一块砖的颜色数，二，三……五

pre是上一次用的颜色是能涂pre块砖头的

因为上一次用的是能涂pre块砖头的，所以这一次涂色里能涂pre-1块砖头的颜色里有一种颜色不能用了

对应的系数就要-1

code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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;

ll dp[16][16][16][16][16][6];
#define NOW dp[a][b][c][d][e][pre]
ll dfs(int a,int b,int c,int d,int e,int pre)
{
	if(NOW) return NOW;
	if(!(a||b||c||d||e)) return NOW;
	if(a>0) NOW+=(a-(pre==2))*dfs(a-1,b,c,d,e,1);
	if(b>0) NOW+=(b-(pre==3))*dfs(a+1,b-1,c,d,e,2);
	if(c>0) NOW+=(c-(pre==4))*dfs(a,b+1,c-1,d,e,3);
	if(d>0) NOW+=(d-(pre==5))*dfs(a,b,c+1,d-1,e,4);
	if(e>0) NOW+=e*dfs(a,b,c,d+1,e-1,5);
	NOW%=MOD;
	return NOW;
}
int n,_,cnt[6];
int main()
{
	for(int i=0;i<=5;i++) dp[0][0][0][0][0][i]=1;
	read(n); for(int i=1;i<=n;i++) read(_),cnt[_]++;
	printf("%lld",dfs(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0));

	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

#define MOD 1000000007

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

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

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;

ll dp[16][16][16][16][16][6];

#define NOW dp[a][b][c][d][e][pre]

ll dfs(int a,int b,int c,int d,int e,int pre)

{

if(NOW) return NOW;

if(!(a||b||c||d||e)) return NOW;

if(a>0) NOW+=(a-(pre==2))*dfs(a-1,b,c,d,e,1);

if(b>0) NOW+=(b-(pre==3))*dfs(a+1,b-1,c,d,e,2);

if(c>0) NOW+=(c-(pre==4))*dfs(a,b+1,c-1,d,e,3);

if(d>0) NOW+=(d-(pre==5))*dfs(a,b,c+1,d-1,e,4);

if(e>0) NOW+=e*dfs(a,b,c,d+1,e-1,5);

NOW%=MOD;

return NOW;

}

int n,_,cnt[6];

int main()

{

for(int i=0;i<=5;i++) dp[0][0][0][0][0][i]=1;

read(n); for(int i=1;i<=n;i++) read(_),cnt[_]++;

printf("%lld",dfs(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0));

return 0;

}

BZOJ1079

@OceanEye7年前

05/27

21:13

BZOJ1123

OceanEye 撰写 BZOJ 树形DP 点双联通分量无回复

点双联通分量乱搞
一遍DFS可以处理出一个点周围的连通分量 [tarjan]
还可以处理出他们的和
尝试用树形DP的思想来思考的话会很简单
但是~~玩点歌姬~~细节打错于是调了很久quq
代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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

struct node
{
	int fa,dfn,mn,siz;
	bool vis;
}pool[N];
#define FA pool[x].fa
#define DFN pool[x].dfn
#define MN pool[x].mn
#define SIZ pool[x].siz
#define VIS pool[x].vis

struct Tedge
{
	int from,to;
	bool use;
	Tedge(int _=0,int __=0) { from=_; to=__; use=0; }
}edge[1000010];
int TOP;
#define E edge[i]
#define TO E.to
#define FROM E.from
#define USE E.use

int e_tot,NXT[1000010],fst[N];

void add_e(const int &a,const int &b)
{
	edge[e_tot]=Tedge(a,b); NXT[e_tot]=fst[a]; fst[a]=e_tot++;
	edge[e_tot]=Tedge(b,a); NXT[e_tot]=fst[b]; fst[b]=e_tot++;
}

void cp(int &x,int y) { x>y?x=y:x=x; }

ll ans[N];
int cd,n,m;
void tarjan(int x)
{
	DFN=MN=++cd; VIS=true;
	SIZ++;
	int pcnt=0;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(USE||TO==FA) continue;
		USE=true; i^=1; USE=true; i^=1;
		if(!pool[TO].vis)
		{
			pool[TO].fa=x;
			tarjan(TO);
			cp(MN,pool[TO].mn);
			if(pool[TO].mn>=DFN)
			{
				ans[x]+=(ll)pcnt*pool[TO].siz;
				pcnt+=pool[TO].siz;
			}
			SIZ+=pool[TO].siz;
		}
		else cp(MN,pool[TO].dfn);
	}
	ans[x]+=(ll)(n-pcnt-1)*pcnt;
}

int main()
{
	freopen("BZOJ1123.in","r",stdin);
	int __,_;
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	while(m--)
	{
		read(_); read(__);
		add_e(_,__);
	}
	tarjan(1);
	for(int i=1;i<=n;i++) printf("%lld\n",(ans[i]+(n-1))*2);
	return 0;
}

100

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

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

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

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

struct node

{

int fa,dfn,mn,siz;

bool vis;

}pool[N];

#define FA pool[x].fa

#define DFN pool[x].dfn

#define MN pool[x].mn

#define SIZ pool[x].siz

#define VIS pool[x].vis

struct Tedge

{

int from,to;

bool use;

Tedge(int _=0,int __=0) { from=_; to=__; use=0; }

}edge[1000010];

int TOP;

#define E edge[i]

#define TO E.to

#define FROM E.from

#define USE E.use

int e_tot,NXT[1000010],fst[N];

void add_e(const int &a,const int &b)

{

edge[e_tot]=Tedge(a,b); NXT[e_tot]=fst[a]; fst[a]=e_tot++;

edge[e_tot]=Tedge(b,a); NXT[e_tot]=fst[b]; fst[b]=e_tot++;

}

void cp(int &x,int y) { x>y?x=y:x=x; }

ll ans[N];

int cd,n,m;

void tarjan(int x)

{

DFN=MN=++cd; VIS=true;

SIZ++;

int pcnt=0;

for(int i=fst[x];~i;i=NXT[i])

{

if(USE||TO==FA) continue;

USE=true; i^=1; USE=true; i^=1;

if(!pool[TO].vis)

{

pool[TO].fa=x;

tarjan(TO);

cp(MN,pool[TO].mn);

if(pool[TO].mn>=DFN)

{

ans[x]+=(ll)pcnt*pool[TO].siz;

pcnt+=pool[TO].siz;

}

SIZ+=pool[TO].siz;

}

else cp(MN,pool[TO].dfn);

}

ans[x]+=(ll)(n-pcnt-1)*pcnt;

}

int main()

{

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

int __,_;

memset(fst,-1,sizeof(fst));

read(n); read(m);

while(m--)

{

read(_); read(__);

add_e(_,__);

}

tarjan(1);

for(int i=1;i<=n;i++) printf("%lld\n",(ans[i]+(n-1))*2);

return 0;

}

BZOJ1123

@OceanEye7年前

05/24

21:29

BZOJ4591

OceanEye 撰写 BZOJ 数学无回复

代码

无脑用Lucas化简分类后分段递归处理

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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;

// lucas C(n/m)%p = C(n/p,m/p)*C(n%p,m%p)%p

#define MOD 2333
#define M MOD+100
int sum[M][M],c[M][M];

void Dec(int &x) { while(x>=MOD) x-=MOD; }

void pre()
{
	c[0][0]=sum[0][0]=1;
	For(i,1,MOD-1) sum[0][i]=1;
	For(i,1,MOD-1)
	{
		c[i][0]=sum[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1]),Dec(c[i][j]);
		for(int j=1;j<MOD;j++) sum[i][j]=(sum[i][j-1]+c[i][j]),Dec(sum[i][j]);
	}
}

int calc_single(ll n,ll m)
{
	if(m<0||n<m) return 0;
	if(m<MOD&&n<MOD) return c[n][m];
	int ret=1,_,__;
	for(;n&&m&&ret;n/=MOD,m/=MOD)
	{
		_=n%MOD; __=m%MOD;
		if(_<__) return 0;
		ret*=c[_][__]; ret%=MOD;
	}
	return ret;
//	return calc_single(n/MOD,m/MOD)*c[n%MOD][m%MOD]%MOD;
}

int calc(ll n,ll k)
{
	if(k<0) return 0;
	return (calc(n/MOD,k/MOD-1)*sum[n%MOD][MOD-1]%MOD+sum[n%MOD][k%MOD]*calc_single(n/MOD,k/MOD)%MOD)%MOD;
}

int main()
{
	ll t,n,k;
	pre();
	for(read(t);t;t--)
	{
		read(n); read(k);
		printf("%d\n",calc(n,k));
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

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

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

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;

// lucas C(n/m)%p = C(n/p,m/p)*C(n%p,m%p)%p

#define MOD 2333

#define M MOD+100

int sum[M][M],c[M][M];

void Dec(int &x) { while(x>=MOD) x-=MOD; }

void pre()

{

c[0][0]=sum[0][0]=1;

For(i,1,MOD-1) sum[0][i]=1;

For(i,1,MOD-1)

{

c[i][0]=sum[i][0]=1;

for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1]),Dec(c[i][j]);

for(int j=1;j<MOD;j++) sum[i][j]=(sum[i][j-1]+c[i][j]),Dec(sum[i][j]);

}

int calc_single(ll n,ll m)

{

if(m<0||n<m) return 0;

if(m<MOD&&n<MOD) return c[n][m];

int ret=1,_,__;

for(;n&&m&&ret;n/=MOD,m/=MOD)

{

_=n%MOD; __=m%MOD;

if(_<__) return 0;

ret*=c[_][__]; ret%=MOD;

}

return ret;

// return calc_single(n/MOD,m/MOD)*c[n%MOD][m%MOD]%MOD;

}

int calc(ll n,ll k)

{

if(k<0) return 0;

return (calc(n/MOD,k/MOD-1)*sum[n%MOD][MOD-1]%MOD+sum[n%MOD][k%MOD]*calc_single(n/MOD,k/MOD)%MOD)%MOD;

}

int main()

{

ll t,n,k;

pre();

for(read(t);t;t--)

{

read(n); read(k);

printf("%d\n",calc(n,k));

}

return 0;

}

BZOJ4591

@OceanEye7年前

05/24

13:18

BZOJ2982

OceanEye 撰写 BZOJ 数学模板模版题无回复

Lucas定理裸题

恩具体证明请百度 Lucas定理

刚刚发现我是RK3 :-D高兴

//---------------OceanEye's Code----------------------//
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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 MOD 10007
#define M MOD+100
int pre[M];
void init()
{
	pre[0]=1;
	for(int i=1;i<=MOD;i++) pre[i]=pre[i-1]*i%MOD;
}

int ksm(int a,int k)
{
	int ret=1;
	for(;k;k>>=1)
	{
		if(k&1) ret=(ret*a)%MOD;
		a*=a; a%=MOD;
	}
	return ret;
}

#define calc_inv(p) (ksm(p,MOD-2))

int comb(int n,int m) { return pre[n]*calc_inv(pre[m]*pre[n-m]%MOD)%MOD; }

int Lucas(int n,int m)
{
	int ret=1,_,__;
	while(n&&m&&ret)
	{
		_=n%MOD; __=m%MOD;
		if(_<__) return 0;
		ret*=comb(_,__); ret%=MOD;
		n/=MOD; m/=MOD;
	}
	return ret;
}

int main()
{
	int t,n,m;
	init();
	for(read(t);t;t--)
	{
		read(n); read(m);
		printf("%d\n",Lucas(n,m));
	}
	return 0;
}

//---------------OceanEye's Code----------------------//

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

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

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

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 MOD 10007

#define M MOD+100

int pre[M];

void init()

{

pre[0]=1;

for(int i=1;i<=MOD;i++) pre[i]=pre[i-1]*i%MOD;

}

int ksm(int a,int k)

{

int ret=1;

for(;k;k>>=1)

{

if(k&1) ret=(ret*a)%MOD;

a*=a; a%=MOD;

}

return ret;

}

#define calc_inv(p) (ksm(p,MOD-2))

int comb(int n,int m) { return pre[n]*calc_inv(pre[m]*pre[n-m]%MOD)%MOD; }

int Lucas(int n,int m)

{

int ret=1,_,__;

while(n&&m&&ret)

{

_=n%MOD; __=m%MOD;

if(_<__) return 0;

ret*=comb(_,__); ret%=MOD;

n/=MOD; m/=MOD;

}

return ret;

}

int main()

{

int t,n,m;

init();

for(read(t);t;t--)

{

read(n); read(m);

printf("%d\n",Lucas(n,m));

}

return 0;

}

BZOJ2982

@OceanEye7年前

05/20

15:36

BZOJ3932

OceanEye 撰写 BZOJ 主席树基础题模版题无回复

裸的主席树

前k个可能是一个优先级的一部分

看代码吧:-D

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#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;
#define N 100010

struct rec
{
	int id,pos,val;
}RRR[N<<1];
int ____;

bool comp(const rec &x,const rec &y)
{ return x.id<y.id; }

int n,m,p;

void pre()
{
	read(n); read(m);
	int _,__,___;
	for(int i=1;i<=n;i++)
	{
		read(_); read(__); read(___);
		RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;
		RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;
	}
	sort(RRR,RRR+____,comp);
}

struct node
{
	int l,r,c[2],cnt;
	ll sum;
}pool[N<<6];
#define L pool[x].l
#define R pool[x].r
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define SUM pool[x].sum
#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)
{
	SUM=pool[Lc].sum+pool[Rc].sum;
	CNT=pool[Lc].cnt+pool[Rc].cnt;
}

void insert(const int &pos,int& x,const int &val)
{
	pool[++pcnt]=pool[x]; x=pcnt;
	if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }
	int mid=(L+R)>>1;
	if(mid>=pos)
	{
		if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;
		insert(pos,Lc,val);
	}
	else
	{
		if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;
		insert(pos,Rc,val);
	}
	PushUP(x);
}

ll sum(int x,int k)
{
	if(x==0) return 0;
	if(CNT<=k) return SUM;
	if(L==R) { return (ll)min(k,CNT)*L; }
	return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);
}

int main()
{
	freopen("BZOJ3932.in","r",stdin);
	pre();
	____=0;
	pool[0].l=1; pool[0].r=10000050;
	for(int i=1;i<=m;i++)
	{
		RT[i]=RT[i-1];
		for(;RRR[____].id==i;____++)
			insert(RRR[____].pos,RT[i],RRR[____].val);
	}
	static int Q,T,A,B,C,k,mid;
	ll pre=1;
	while(m--)
	{
		read(T); read(A); read(B); read(C);
		pre%=C; A%=C; B%=C;
		k=1+(ll)(1LL*A*pre+B)%C;
		printf("%lld\n",pre=sum(RT[T],k));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#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;

#define N 100010

struct rec

{

int id,pos,val;

}RRR[N<<1];

int ____;

bool comp(const rec &x,const rec &y)

{ return x.id<y.id; }

int n,m,p;

void pre()

{

read(n); read(m);

int _,__,___;

for(int i=1;i<=n;i++)

{

read(_); read(__); read(___);

RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;

RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;

}

sort(RRR,RRR+____,comp);

}

struct node

{

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

ll sum;

}pool[N<<6];

#define L pool[x].l

#define R pool[x].r

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

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

#define SUM pool[x].sum

#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)

{

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

CNT=pool[Lc].cnt+pool[Rc].cnt;

}

void insert(const int &pos,int& x,const int &val)

{

pool[++pcnt]=pool[x]; x=pcnt;

if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }

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

if(mid>=pos)

{

if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;

insert(pos,Lc,val);

}

else

{

if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;

insert(pos,Rc,val);

}

PushUP(x);

}

ll sum(int x,int k)

{

if(x==0) return 0;

if(CNT<=k) return SUM;

if(L==R) { return (ll)min(k,CNT)*L; }

return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);

}

int main()

{

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

pre();

____=0;

pool[0].l=1; pool[0].r=10000050;

for(int i=1;i<=m;i++)

{

RT[i]=RT[i-1];

for(;RRR[____].id==i;____++)

insert(RRR[____].pos,RT[i],RRR[____].val);

}

static int Q,T,A,B,C,k,mid;

ll pre=1;

while(m--)

{

read(T); read(A); read(B); read(C);

pre%=C; A%=C; B%=C;

k=1+(ll)(1LL*A*pre+B)%C;

printf("%lld\n",pre=sum(RT[T],k));

}

return 0;

}

BZOJ3932

@OceanEye7年前

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

1 2 下一页

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

@OceanEye7年前

BZOJ1031 [JSOI2007]字符加密Cipher

@OceanEye7年前

BZOJ3329

@OceanEye7年前

BZOJ2243

@OceanEye7年前

Description

Input

Output

Sample Input

Sample Output

HINT

BZOJ3698

@OceanEye7年前

BZOJ1079

@OceanEye7年前

BZOJ1123

@OceanEye7年前

BZOJ4591

@OceanEye7年前

BZOJ2982

@OceanEye7年前

BZOJ3932

@OceanEye7年前

BZOJ4869

友情链接

近期文章

标签