发表于 | 更新于

Link

Solution

嗯。我经过一个来小时的思考，搞出来一种状态表示：在线段树的每个节点记录一个2x2的矩阵，表示a[0][1]表示左端两点不联通，右端两点联通，a[1][1]表示左端两点联通，右端两点联通，etc。画了几个图，感觉比较资磁，开始写。写了一会儿发现被一些细节边界什么的卡住了，觉得自己方法可能错了。 一看果然和标解不同。标解特别特别复杂，网上的题解也都很麻烦。于是%faebdc的AC程序（在考场上写出的程序中他的是最快的，比std快三倍orz。。）。看懂之后发现姜志豪大爷的做法跟我的想法是一样的！！ 然后发现，我是因为想用一些简单的办法算出后继状态而被自己克死的（见注释）。。。 改成正常的推法，枚举一下，就A了。。

Tips

开始写之前尽量把边界情况想出来 不要怕麻烦 用最直观的方法先实现出来，再考虑合并代码

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=60000+10,CON=1,DIC=0,INF=INT_MAX;
using std::swap;
using std::min;

struct iMe
{
	int v[2][2];
	int mind,sumd;
	int *operator [](int x){return v[x];}
};
/*
iMe Merge(const iMe &a,const iMe &b)
{
	iMe r=iMe(INF);
	for(int al=0;al<=1;al++)for(int ar=0;ar<=1;ar++)
		for(int bl=0;bl<=1;bl++)for(int br=0;br<=1;br++)
		{
			int temp=(ar && bl)?a.mind:a.sumd;
			int rl=al | bl,rr=ar | br;
			chkmn(r[rl][rr],a[al][ar]+b[bl][br]+temp);
		}
	return r;
}*/
iMe Merge(iMe a,iMe b)
{
	iMe r;r.mind=b.mind;r.sumd=b.sumd;
	r[1][1]=min(a[1][1]+b[1][1]+a.mind,
				a.sumd+min(a[1][0]+b[1][1],a[1][1]+b[0][1]));
	r[1][0]=min(a[1][1]+b[1][0]+a.mind,
				a.sumd+min(a[1][1]+b[0][0],a[1][0]+b[1][0]));
	r[0][1]=min(a[0][1]+b[1][1]+a.mind,
				a.sumd+min(a[0][0]+b[1][1],a[0][1]+b[0][1]));
	r[0][0]=min(a[0][1]+b[1][0]+a.mind,
				a.sumd+min(a[0][0]+b[1][0],a[0][1]+b[0][0]));
				//a.sumd+min(a[0][0]+b[0][0],
	return r;
}
struct SegmentTree
{
	struct Node
	{
		Node *son[2];
		iMe rec;
		void Fill(int);
		void up(){rec=Merge(son[0]->rec,son[1]->rec);}
	}*null,*root,*ME;int TL,TR;
	SegmentTree()
	{
		null=new Node;
		ME=new Node[MAXN<<2];
		null->son[0]=null->son[1]=null;
		root=null;
	}
	Node *newNode()
	{
		Node *cur=ME++;
		cur->son[0]=cur->son[1]=null;
		return cur;
	}
	void Build(Node *&,int,int);
	void Build(int n)
	{
		TL=1,TR=n;
		Build(root,1,n);
	}
	void Edit(Node *,int,int,int);
	void F5(int pos){Edit(root,TL,TR,pos);}
	iMe Access(Node*,int,int,int,int);
	iMe Access(int L,int R){return Access(root,TL,TR,L,R);}
}Tree;
int tor[3][MAXN],tod[MAXN];
void SegmentTree::Node::Fill(int pos)
{
	rec.mind=min(tor[1][pos],tor[2][pos]);
	rec.sumd=tor[1][pos]+tor[2][pos];
	rec[0][0]=rec[0][1]=rec[1][0]=0;
	rec[1][1]=tod[pos];
}
void SegmentTree::Build(Node *&pos,int L,int R)
{
	pos=newNode();
	if(L==R)
		pos->Fill(L);
	else
	{
		int MID=(L+R)>>1;
		Build(pos->son[0],L,MID);
		Build(pos->son[1],MID+1,R);
		pos->up();
	}
}
void SegmentTree::Edit(Node *pos,int L,int R,int goal)
{
	if(L==R)
		pos->Fill(L);
	else
	{
		int MID=(L+R)>>1;
		if(goal<=MID)
			Edit(pos->son[0],L,MID,goal);
		else
			Edit(pos->son[1],MID+1,R,goal);
		pos->up();
	}
}
iMe SegmentTree::Access(Node *pos,int L,int R,int l,int r)
{
	if(L==l && R==r) return pos->rec;
	else
	{
		int MID=(L+R)>>1;
		if(r<=MID) return Access(pos->son[0],L,MID,l,r);
		else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
		else return Merge(Access(pos->son[0],L,MID,l,MID),Access(pos->son[1],MID+1,R,MID+1,r));
	}
}
int main()
{
	//freopen("input","r",stdin);
	int n,m;get(n),get(m);
	for(int i=1;i<=n-1;i++) get(tor[1][i]);
	for(int i=1;i<=n-1;i++) get(tor[2][i]);
	for(int i=1;i<=n;i++) get(tod[i]);
	Tree.Build(n);
	for(int i=1;i<=m;i++)
	{
		char opt;int x0,y0,x1,y1,w,L,R;
		while(!isalpha(opt=getchar()));
		if(opt=='Q')
		{
			get(L),get(R);
			printf("%d\n",Tree.Access(L,R)[1][1]);
		}
		else
		{
			get(x0),get(y0),get(x1),get(y1),get(w);
			if(x0>x1 || (x0==x1 && y0>y1)) swap(x0,x1),swap(y0,y1);
			if(x0+1==x1) tod[y0]=w;
			else tor[x0][y0]=w;
			Tree.F5(y0);
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

发表于 | 更新于

Link

就是这么一道题让我搭上了几乎一天。。

Solution

个人感觉两步都很难啊。 首先，给定∑xi=N\sum x_i=N这样的方程，如果是求正整数解的方案数目是很好求的。 对于xi≥aix_i\ge a_i的限制，可以直接把总和−(ai−1)-(a_i-1)，相当于把ai−1a_i-1钦定给了xix_i，就可以转化为正整数解了。 对于xi≤aix_i\le a_i的限制就诡了。正解是容斥，设f(...)f(...)为钦定......不满足条件的方案数目，那么Ans=f()−∑f(i)+∑∑f(i,j)−∑∑∑f(i,j,k)...Ans=f()-\sum f(i)+\sum\sum f(i,j)-\sum\sum\sum f(i,j,k)... 之前没怎么研究过容斥的题目，感觉这个条件给的很玄。 于是我查了查资料，翻了翻书，在《组合数学》里的一句话启发了我：

AiA_i是SS中具有性质PiP_i(也可能还具有其他的一些性质)的子集

这样，某个xix_i一定不对就是一个这样的性质。 至于第二步，就是这篇文章了；

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10;
typedef long long LL;
int P;
inline int Pow(int a,int v)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res*=a;
		a*=a;
		v>>=1;
	}
	return res;
}
inline int Pow(int a,int v,int P)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res=(LL)res*a%P;
		a=(LL)a*a%P;
		v>>=1;
	}
	return res;
}
int exgcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int d=exgcd(b,a%b,x,y);
		LL nx=y,ny=x-(a/b)*y;
		x=nx,y=ny;
		return d;
	}
}
inline int inv(int a,int n)
{
	LL x,y;exgcd(a,n,x,y);
	return (x%n+n)%n;
}
namespace iLucas
{
	int P,dc;
	int dv[MAXN],dt[MAXN],dvt[MAXN];
	//A[]
	//M[i]=M/m[i]
	//t[i]*M[i]=1 (mod m[i])
	int A[MAXN],M[MAXN],t[MAXN],m[MAXN],tM[MAXN];
	const int FN=1e5,MAXF=FN+10;
	int table[MAXN][MAXF];
	inline void Add(int np,int &x)
	{
		++dc;dv[dc]=np;dt[dc]=0,dvt[dc]=1;
		while(x%np==0) dt[dc]++,x/=np,dvt[dc]*=np;
		int *ptr=table[dc];ptr[0]=1;
		for(int i=1;i<=dvt[dc];i++)
			if(i%np==0) ptr[i]=ptr[i-1];
			else ptr[i]=(LL)ptr[i-1]*i%dvt[dc];
		m[dc]=dvt[dc];M[dc]=P/m[dc];t[dc]=inv(M[dc],m[dc]);
		tM[dc]=(LL)t[dc]*M[dc]%P;
	}
	inline void Init(int x)
	{
		P=x;
		for(int i=2;i*i<=x;i++)
			if(x%i==0) Add(i,x);
		if(x!=1) Add(x,x);
	}
	int Calc(int n,int idx)
	{
		int *ptr=table[idx],v=dv[idx],vt=dvt[idx];
		if(n<v) return ptr[n];
		return (LL)Calc(n/v,idx)*Pow(ptr[vt],n/vt,vt)*ptr[n%vt]%vt;
	}
	int C(int n,int m,int idx)
	{
		int times,v,t,vt;
		v=dv[idx],t=dt[idx],vt=dvt[idx];times=0;
		for(int i=n;i;i/=v) times+=i/v;
		for(int i=m;i;i/=v) times-=i/v;
		for(int i=n-m;i;i/=v) times-=i/v;
		if(times>=t) return 0;
		else
		{
			int pt,fn,fm,fnmm;
			pt=Pow(v,times);
			fn=Calc(n,idx),fm=Calc(m,idx),fnmm=Calc(n-m,idx);
			return (LL)pt*fn*inv(fm,vt)*inv(fnmm,vt)%vt;
		}
	}
	inline int CRT()
	{
		int res=0;
		for(int i=1;i<=dc;i++) res=((LL)A[i]*tM[i]+res)%P;
		return res;
	}
	inline int C(int n,int m)
	{
		if(n<m) return 0;
		for(int i=1;i<=dc;i++) A[i]=C(n,m,i);
		return CRT();
	}
}
int a[MAXN],ac,n,m;
//前ac个数<=a[i] 所有的数>=1的方案数
void WORK()
{
	int n1,n2,t;
	get(n),get(n1),get(n2),get(m);
	for(int i=1;i<=n1;i++) get(a[i]);
	ac=n1;
	for(int i=1;i<=n2;i++) get(t),m-=t-1;
	int sum,cnt,ANS=0,res;
	for(int i=(1<<n1)-1;~i;i--)
	{
		sum=m,cnt=0;
		for(int j=1;j<=ac;j++)
			if(i&(1<<j>>1)) cnt++,sum-=a[j];
		res=iLucas::C(sum-1,n-1);
		if(cnt&1) ANS-=res,((ANS%=P)+=P)%=P;
		else ANS+=res,ANS%=P;
	}
	printf("%d\n",ANS);
}
int main()
{
	int T;get(T),get(P);iLucas::Init(P);
	while(T--) WORK();
	return 0;
}
/* AC Record(Bugs) *
 * WA baoint +=
 * WA invine 
 * * * * * * * * * */

发表于 | 更新于

Link

至于这个就比模拟退火更玄学了。。几乎完全取决于一开始选择的起点。。不得要领。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10000+100;
template <class T> inline T sqr(T x){return x*x;}
struct poi{int x,y;}p[MAXN];int w[MAXN],n;
double calc(double x,double y)
{
	double res=0;
	for(int i=1;i<=n;i++) res+=sqrt(sqr(x-p[i].x)+sqr(y-p[i].y))*w[i];
	return res;
}
double frand()
{
	return ((double)rand()/RAND_MAX)*(rand()&1?1:-1);
}
int main()
{
	srand(522133279);
	get(n);double x=0,y=0;
	for(int i=1;i<=n;i++) 
	{
		get(p[i].x),get(p[i].y),get(w[i]);
		//x+=p[i].x*w[i],y+=p[i].y*w[i];
		x+=p[i].x,y+=p[i].y;
	}
	x/=n,y/=n;double ANS=calc(x,y),cx=x,cy=y,tx,ty;
	for(double step=1e5;step>1e-5;step*=0.98)
	{
		tx=cx+frand()*step,ty=cy+frand()*step;
		double res=calc(tx,ty);
		if(chkmn(ANS,res))
			x=tx,y=ty;
		if(calc(cx,cy)>res)
			cx=tx,cy=ty;
	}
	printf("%.3lf %.3lf\n",x,y);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

发表于 | 更新于

Link

Solution

可以发现最短路程就是连接所有的宝物的一棵生成树的边权和×2\times 2 修改一个节点只会影响DFS序在它两边的点，可以用Treap维护。 然后就可做了。

Tips

看出了DFS序，可是硬要实时地维护生成树的边权和，结果用正常的DFS序就做不了了。 发现正解直接维护相邻点的距离和，最后再加上最靠左的和最靠右的点的距离。。简单粗暴解决问题。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10,LOG=30,INF=0x1f1f1f1f;
typedef long long LL;
using std::swap;
using std::pair;
using std::make_pair;
struct Edge{int to,v,pre;}e[MAXN<<1];int id[MAXN],ec;
void Adde(int f,int t,int v)
{
	e[++ec].to=t;e[ec].v=v;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].v=v;e[ec].pre=id[t];id[t]=ec;
}
LL dist[MAXN];int dfn[MAXN];
namespace STLCA
{
	int dc,dep[MAXN],dfs[MAXN<<1],li[MAXN],ro[MAXN],dfndc;
	void DFS(int pos)
	{
		dfn[pos]=++dfndc;
		dfs[li[pos]=ro[pos]=++dc]=pos;
		for(int i=id[pos];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(dep[u]) continue;
			dep[u]=dep[pos]+1;dist[u]=dist[pos]+e[i].v;
			DFS(u);dfs[++dc]=pos;ro[pos]=ro[u];
		}
		
	}
	int f[MAXN<<1][LOG],log_2[MAXN<<1]; 
	void ST()
	{
		log_2[0]=-1;
		for(int i=1;i<=dc;i++)
		{
			f[i][0]=dfs[i];
			log_2[i]=log_2[i>>1]+1;
		}
		for(int j=1;j<=log_2[dc];j++)
			for(int i=1;i<=dc-(1<<j)+1;i++)//j++
			{
				int pl=f[i][j-1],pr=f[i+(1<<j>>1)][j-1];
				f[i][j]=dep[pl]<dep[pr]?pl:pr;
			}
	}
	void Init()
	{
		dep[1]=1;DFS(1);ST();
	}
	int LCA(int p1,int p2)
	{
		p1=li[p1],p2=li[p2];
		if(p1>p2) swap(p1,p2);
		int gol=log_2[p2-p1+1],pl=f[p1][gol],pr=f[p2-(1<<gol)+1][gol];
		return dep[pl]<dep[pr]?pl:pr; 
	}
}
LL Dis(int p1,int p2)
{
	using namespace STLCA;
	if(!p1 || !p2) return 0;
	return dist[p1]+dist[p2]-dist[LCA(p1,p2)]*2;
}
const int P=1e5+7;
struct Treap
{
	struct Node
	{
		Node *son[2];
		int py,sz;pair<int,int> v;
		void up(){sz=son[0]->sz+son[1]->sz+1;}
	}*null,*root;
	Treap()
	{
		null=new Node();
		null->son[0]=null->son[1]=null;
		null->py=P;null->sz=0;
		root=null;
	}
	int size(){return root->sz;}
	Node *newNode(pair<int,int> v)
	{
		static Node *ME=new Node[MAXN],*cur;
		cur=ME++;cur->v=v;cur->py=rand()%P;
		cur->sz=1;cur->son[0]=cur->son[1]=null;
		return cur;
	}
	void trans(Node *&pos,int d)
	{
		Node *s=pos->son[d];
		pos->son[d]=s->son[!d];
		s->son[!d]=pos;pos->up(),s->up();
		pos=s;
	}
	int adjust(Node *&pos)
	{
		int d=pos->son[0]->py>pos->son[1]->py;
		if(pos->py>pos->son[d]->py)
		{
			trans(pos,d);
			return !d;
		}
		else return -1;
		//return -1;
	}
	void Insert(Node *&pos,pair<int,int> v)
	{
		if(pos==null)
			pos=newNode(v);
		else if(pos->v==v) assert(1);
		else
		{
			int jud=pos->v<v;
			Insert(pos->son[jud],v),pos->up();
			adjust(pos);
		}
	}
	void Insert(pair<int,int> v){Insert(root,v);}
	void DelNode(Node *&pos)
	{
		int d=adjust(pos);
		if(~d)
			DelNode(pos->son[d]),pos->up();
		else
			pos=null;
	}
	void Delete(Node *&pos,pair<int,int> v)
	{
		if(pos->v==v)
		{
			pos->py=P;
			DelNode(pos);//,pos->up();
		}
		else
		{
			int jud=pos->v<v;
			Delete(pos->son[jud],v),pos->up();//无需adjust.?
		}
	}
	void Delete(pair<int,int> v){Delete(root,v);}
	pair<int,int> Pred(pair<int,int> v)
	{
		Node *pos=root;
		pair<int,int> res=make_pair(-INF,0);
		while(pos!=null)
		{
			if(pos->v<v)
			{
				chkmx(res,pos->v);
				pos=pos->son[1];
			}
			else
				pos=pos->son[0];
		}
		return res;
	}
	pair<int,int> Succ(pair<int,int> v)
	{
		Node *pos=root;
		pair<int,int> res=make_pair(INF,0);
		while(pos!=null)
		{
			if(pos->v>v)
			{
				chkmn(res,pos->v);
				pos=pos->son[0];
			}
			else
				pos=pos->son[1];
		}
		return res;
	}
	pair<int,int> First()
	{
		Node *pos=root;
		while(pos->son[0]!=null) pos=pos->son[0];
		return pos->v;
	}
	pair<int,int> Last()
	{
		Node *pos=root;
		while(pos->son[1]!=null) pos=pos->son[1];
		return pos->v;
	}
}S;
bool treasured[MAXN];
LL Adjust(int pos)
{
	static LL res=0;
	treasured[pos]^=1;
	pair<int,int> cur=make_pair(dfn[pos],pos);
	int pred=S.Pred(cur).second,succ=S.Succ(cur).second;
	if(!treasured[pos])//delete
	{
		res-=Dis(pred,pos);
		res-=Dis(succ,pos);
		res+=Dis(pred,succ);
		S.Delete(cur);
	}
	else//insert
	{
		res+=Dis(pred,pos);
		res+=Dis(succ,pos);
		res-=Dis(pred,succ);
		S.Insert(cur);
	}
	return res+Dis(S.First().second,S.Last().second);
	//当问题被自己转化地做不了 要回头试试
}
int main()
{
	//freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int n,m;get(n),get(m);
	for(int i=1;i<=n-1;i++)
	{
		int x,y,z;get(x),get(y),get(z);
		Adde(x,y,z);
	}
	STLCA::Init();
	for(int i=1;i<=m;i++)
	{
		int t;get(t);
		printf("%lld\n",Adjust(t));
	}
	return 0;
}
/* AC Record(Bugs) *
 * WA null有了sz..一定要注意null会不会被pushup 
 * * * * * * * * * */

发表于 | 更新于

Link

Solution

可并堆最右链的长度最长为O(logn)O(\log n)，而左链没有任何限制。

和平衡树相比，左偏树采取了与平衡树完全相反的构造策略。平衡树为了实现所有元素的快速查找，使节点尽量趋于平衡。而左偏树的目的是实现快速的查询最小值与合并操作，恰恰要让节点尽量向左偏。最优的平衡树，恰恰是最差的左偏树，而最优的左偏树，恰恰是平衡树退化的结果。--BYVoid

事实是，左偏树中的任何一条从根到到叶节点的链，上面的点的相对深度关系都永远不会变化，也就是说，这条链只能变长，不会变短。假如一直把一个堆和另一个比它堆顶还大的元素合并，最终就会出来一条链。 所以这道题用左偏树的做法复杂度是有问题的，但出题人没有卡。 做法就按照各种操作的步骤来就行了，只是全局最大值要用一个Treap记录所有堆顶的值，每次O(logn)O(\log n)找最大。在修改堆的时候相应修改Treap中的元素，就可以了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
211
212
213
214
215
216
217
218
219
220
221
222
223
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=300000+10;
using std::pair;
using std::make_pair;
using std::swap;

namespace iTreap
{
	const int SIZE=MAXN<<1,P=1e5+7;
	typedef pair<int,int> Data;
	struct Node
	{
		Node *son[2];
		Data v;int py;
		Node(){son[0]=son[1]=0;py=P;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null;
	Node* newNode(Data v)
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;cur->v=v;cur->py=rand()%P;
		return cur;
	}
	void trans(Node *&pos,int d)
	{
		Node *s=pos->son[d];
		pos->son[d]=s->son[!d],s->son[!d]=pos;
		pos=s;
	}
	int adjust(Node *&pos)
	{
		int jud=pos->son[0]->py>pos->son[1]->py;
		if(pos->py>pos->son[jud]->py)
			trans(pos,jud),jud^=1;
		else jud=-1;return jud;
	}
	void DelNode(Node *&pos)
	{
		int d=adjust(pos);
		if(~d) DelNode(pos->son[d]);
		else pos=null;
	}
	void Delete(Node *&pos,const Data &v)
	{
		if(pos==null) assert(1);
		if(pos->v==v) pos->py=P,DelNode(pos);
		else Delete(pos->son[pos->v<v],v);
	}
	void Insert(Node *&pos,const Data &v)
	{
		if(pos==null) pos=newNode(v);
		else if(v==pos->v) assert(1);
		else Insert(pos->son[pos->v<v],v),adjust(pos);
	}
	Data Max()
	{
		Node *pos=root;
		while(pos->son[1]!=null) pos=pos->son[1];
		return pos->v;
	}
}using namespace iTreap;
namespace iLet
{
	const int SIZE=MAXN;
	struct Node
	{
		Node *son[2],*fa;
		int v,add,id,dist;
		Node(){v=-INT_MAX;dist=id=add=0;}
		bool kind(){return fa->son[1]==this;}
		void down();
		void up();
		void Add(int d)
		{
			add+=d;
			v+=d;
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*node[MAXN];
	//并查集不好哢
	void InitPtr(Node *pos)
	{
		pos->son[0]=pos->son[1]=pos->fa=null;
		pos->dist=pos->add=0;
	}
	void Init(int i,int v)
	{
		node[i]=new(ME++) Node;
		node[i]->v=v;node[i]->id=i;
		InitPtr(node[i]);
	}
	void Node::up()
	{
		son[0]->fa=son[1]->fa=this;
		dist=son[1]->dist+1;
	}
	void Node::down()
	{
		if(add)
		{
			if(son[0]!=null) son[0]->Add(add);
			if(son[1]!=null) son[1]->Add(add);
			add=0;
		}
	}
	Node *Merge(Node *a,Node *b)
	{
		if(a==null) return b;
		if(b==null) return a;
		a->down(),b->down();
		if(a->v<b->v) swap(a,b);
		a->son[1]=Merge(a->son[1],b);
		if(a->son[0]->dist<a->son[1]->dist) swap(a->son[0],a->son[1]);
		a->up();
		return a;
	}
	Node *Root(Node *pos){return pos->fa==null?pos:Root(pos->fa);}
	Node *Root(int pos){return Root(node[pos]);}
	void markdown(Node *pos)
	{
		if(pos->fa!=null) markdown(pos->fa);
		pos->down();
	}
	Node *valup(Node *pos)
	{
		pos->up();
		return pos->fa!=null?valup(pos->fa):pos;
	}
	Node *Delete(Node *pos)
	{
		markdown(pos);
		Node *rt=Merge(pos->son[0],pos->son[1]);
		if(pos->fa!=null) 
		{
			pos->fa->son[pos->kind()]=rt;
			rt=valup(pos->fa);
		}
		else rt->fa=null;
		InitPtr(pos);
		return rt;
	}
}using namespace iLet;
void Merge(int p1,int p2)
{
	iLet::Node *r1=Root(p1),*r2=Root(p2);
	if(r1==r2) return;
	iTreap::Delete(root,make_pair(r1->v,r1->id));
	iTreap::Delete(root,make_pair(r2->v,r2->id));
	iLet::Node *rt=Merge(r1,r2);
	Insert(root,make_pair(rt->v,rt->id));
}
void Modify(int pos,int v)
{
	iLet::Node *rt=Root(pos);
	iTreap::Delete(root,make_pair(rt->v,rt->id));
	rt=iLet::Delete(node[pos]);
	node[pos]->v+=v;
	rt=Merge(node[pos],rt);
	iTreap::Insert(root,make_pair(rt->v,rt->id));
}
void AddAll(int pos,int v)
{
	iLet::Node *rt=Root(pos);
	iTreap::Delete(root,make_pair(rt->v,rt->id));
	rt->Add(v);
	iTreap::Insert(root,make_pair(rt->v,rt->id));
}
int main()
{
	static int a[MAXN];
	int n,delta=0;get(n);
	for(int i=1;i<=n;i++)
	{
		get(a[i]);
		Insert(root,make_pair(a[i],i));
		Init(i,a[i]);
	}
	int	Q;get(Q);char opt[10];int x,y,v;
	for(int i=1;i<=Q;i++)
	{
		scanf("%s",opt);
		if(opt[0]=='U') get(x),get(y),Merge(x,y);
		else if(opt[0]=='A')
			if(opt[1]=='1')
			{
				get(x),get(v);
				Modify(x,v);
			}
			else if(opt[1]=='2')
			{
				get(x),get(v);
				AddAll(x,v);
			}
			else
			{
				get(v),delta+=v;
			}
		else
			if(opt[1]=='1')
			{
				get(x);markdown(node[x]);
				printf("%d\n",node[x]->v+delta);
			}
			else if(opt[1]=='2')
			{
				get(x);
				printf("%d\n",Root(x)->v+delta);
			}
			else
			{
				printf("%d\n",Max().first+delta);
			}
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE 没有判断联通性
 * RE sizeof Treap too small;
 * RE origin father ptr wasn't cut off
 * * * * * * * * * */

发表于 | 更新于

据说提答题很好用，所以学习一个。。

爬山

Problem

最典型的例子：给定一个函数，求最值。

Solution

单峰函数，可以用三分法，但如果函数没什么特殊的性质就不好弄了。 于是开启蛮力/乱搞模式。 一个函数图像

发表于 | 更新于

做法来自jianglangcaijin

Problem

求 是 质 数

Solution

实在没看出扩展在哪。。和Lucas有任何相似之处吗。。。 看了很久才看懂啊。。。太弱了。 首先，如果可以分别求出来 ，用中国剩余定理就可以 质 因 数 个 数 地解出来了。 现在的问题是要求 是 质 数 。 而Cnm=n!m!(n−m)!C_n^m=\dfrac {n!}{m!(n-m)!} 而xx有关于yy的逆元，当且仅当gcd(x,y)==1\gcd(x,y)==1 所以要把除以分母变成乘它的逆元，必须先把分母中的含有的pp的幂先处理掉。 现在单独看n!n!的话

n!=∏p∤ii×p[pn][np]!n!=\prod_{p\nmid i}i\times p^{[\dfrac pn]}[\frac np]!

以n=10,p=3n=10,p=3为例 10!=1×2×..×9×1010!=1\times 2\times ..\times 9\times 10 把33的倍数提出来，就是 10!=1×2×4×5×7×8×10×33(1×2×3)10!=1\times 2\times 4\times 5\times7\times8\times10\times 3^3(1\times2\times3) 分别考虑这些项 [np]![\dfrac np]!递归处理 的值是循环的，每一段[i+1,i×pt][i+1,i\times p^t]区间的乘积 是相等的(不会证明啊。。求证明啊。。)，于是就可以循环部分用快速幂，超出循环的部分直接累乘。 而p[pn]p^{[\dfrac pn]}就是需要处理掉的部分，每一层递归的p[pn]p^{[\dfrac pn]}累乘起来就是在n!n!出现的所有pp了。 可以直接整体地把n!n!的质因子分解中pp的次数reprep求出来，把prepp^{rep}从阶乘中提出来，就可以消除其影响了。 于是就得到了上面问题的解决方法： 把n!,m!,(n−m)!n!,m!,(n-m)!中pp的次数repn,repm,repn−mrep_n,rep_m,rep_{n-m}分别求出来，而这个是比较好求的。幂的相除相当于指数相减，所以CnmC_n^m中包含的pp的次数为repn−repm−repn−mrep_n-rep_m-rep_{n-m}。消除了pp的影响，对剩下的两项递归求解即可。 呃虽然好求我也是看了一会儿才懂。。 

1
for(int i=n;i;i/=p) res+=i/p;

直观地感受一下，当i==ni==n时，i/pi/p求的是ii之内有多少个数字的是pp的倍数，i/=pi/=p相当于把ii以内的数集体/p/p，这样只含p1p^1的数字就被干掉了，剩下的数字继续进行这个过程。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100;
typedef long long LL;
int P;
int Pow(int a,int v)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res*=a;
		a*=a;
		v>>=1;
	}
	return res;
}
int Pow(int a,int v,int P)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res=(LL)res*a%P;
		a=(LL)a*a%P;
		v>>=1;
	}
	return res;
}
int exgcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int d=exgcd(b,a%b,x,y);
		LL nx=y,ny=x-(a/b)*y;
		x=nx,y=ny;
		return d;
	}
}
int inv(int a,int n)
{
	LL x,y;
	int d=exgcd(a,n,x,y);
	assert(d==1);
	return (x%n+n)%n;
}
namespace iLucas
{
	int P,dc;
	int dv[MAXN],dt[MAXN],vt[MAXN];
	//A[]
	//M[i]=M/m[i]
	//t[i]*M[i]=1 (mod m[i])
	int A[MAXN],M[MAXN],t[MAXN],m[MAXN],tM[MAXN];
	void Add(int np,int &x)
	{
		dv[++dc]=np,dt[dc]=0;
		while(x%np==0) dt[dc]++,x/=np;
		m[dc]=vt[dc]=Pow(dv[dc],dt[dc]);
	}
	void Init(int x)
	{
		P=x;
		for(int i=2;i*i<=x;i++) if(x%i==0) Add(i,x);
		if(x!=1) Add(x,x);
		int pM=1;//pi M<x
		for(int i=1;i<=dc;i++) pM*=m[i];
		for(int i=1;i<=dc;i++)
		{
			M[i]=pM/m[i];
			t[i]=inv(M[i],m[i]);
			tM[i]=(LL)M[i]*t[i]%P;
		}
	}
	int Calc(int n,int v,int t)
	{
		if(n==0) return 1;
		int vt=Pow(v,t),prod=1;
		for(int i=1;i<=vt;i++)
			if(i%v) prod=(LL)prod*i%vt;
		int rpt=n/vt,res=Pow(prod,rpt,vt);
		for(int i=rpt*vt+1;i<=n;i++)
			if(i%v) res=(LL)res*i%vt;
		return (LL)res*Calc(n/v,v,t)%vt;
	}
	int C(int n,int m,int v,int t)//C(n,m) mod v^t
	{
		int vt=Pow(v,t),vtot=0;
		for(int i=n;i;i/=v) vtot+=i/v;
		for(int i=m;i;i/=v) vtot-=i/v;
		for(int i=n-m;i;i/=v) vtot-=i/v;
		int prod=Pow(v,vtot,vt),
			cn=Calc(n,v,t),
			cm=Calc(m,v,t),
			cnmm=Calc(n-m,v,t);
		return (LL)prod*cn*inv(cm,vt)*inv(cnmm,vt)%vt;
	}
	int CRT()
	{
		int res=0;
		for(int i=1;i<=dc;i++) res=((LL)A[i]*tM[i]%P+res)%P;
		return res;
	}
	int C(int n,int m)
	{
		for(int i=1;i<=dc;i++) A[i]=C(n,m,dv[i],dt[i]);
		return CRT();
	}
}
int C(int n,int m)
{
	if(n<m) return 0;
	return iLucas::C(n,m);
}
bool ud[MAXN];
int a[MAXN],ac,n,m;
//前ac个数<=a[i] 所有的数>=1的方案数
int calc()
{
	int sum=m,cnt=0;
	for(int i=1;i<=ac;i++)
		if(ud[i]) cnt++,sum-=a[i];
	int res=C(sum-1,n-1);
	if(cnt&1)//奇数
		res=((P-res)%P+P)%P;
	return res;
}
int DFS(int pos)
{
	if(pos==ac+1)
		return calc();
	else
	{
		int res=0;
		ud[pos]=0;res=((LL)res+DFS(pos+1))%P;
		ud[pos]=1;res=((LL)res+DFS(pos+1))%P;//+=
		return res;
	}
}
void WORK()
{
	int n1,n2,t;
	get(n),get(n1),get(n2),get(m);
	for(int i=1;i<=n1;i++) get(a[i]);
	ac=n1;
	for(int i=1;i<=n2;i++) get(t),m-=t-1;
	printf("%d\n",DFS(1));
}
int main()
{
	int T;get(T),get(P);iLucas::Init(P);
	while(T--) WORK();
	return 0;
}

貌似跑得很慢。应该还有更优的做法。待进一步研究。 学习了一下别人的写法，学到了这些

小小的优化

  1. 对 一 个 合 适 的 值 的 值打表。
  2. 如果算出来的repn−repm−repn−mrep_n-rep_m-rep_{n-m}比当前需要算的tt（即模数ptp^t的指数）还大，直接返回0。

彻底改进

对于每个数质因子pip_i，预处理table[i][]table[i][]

table[i][j]=∏pi∤k,k<jktable[i][j]=\prod_{p_i\nmid k,k<j}k

上面的很多东西就O(1)O(1)查表即可。见Code。

Modified Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10;
typedef long long LL;
int P;
inline int Pow(int a,int v)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res*=a;
		a*=a;
		v>>=1;
	}
	return res;
}
inline int Pow(int a,int v,int P)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res=(LL)res*a%P;
		a=(LL)a*a%P;
		v>>=1;
	}
	return res;
}
int exgcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int d=exgcd(b,a%b,x,y);
		LL nx=y,ny=x-(a/b)*y;
		x=nx,y=ny;
		return d;
	}
}
inline int inv(int a,int n)
{
	LL x,y;exgcd(a,n,x,y);
	return (x%n+n)%n;
}
namespace iLucas
{
	int P,dc;
	int dv[MAXN],dt[MAXN],dvt[MAXN];
	//A[]
	//M[i]=M/m[i]
	//t[i]*M[i]=1 (mod m[i])
	int A[MAXN],M[MAXN],t[MAXN],m[MAXN],tM[MAXN];
	const int FN=1e5,MAXF=FN+10;
	int table[MAXN][MAXF];
	inline void Add(int np,int &x)
	{
		++dc;dv[dc]=np;dt[dc]=0,dvt[dc]=1;
		while(x%np==0) dt[dc]++,x/=np,dvt[dc]*=np;
		int *ptr=table[dc];ptr[0]=1;
		for(int i=1;i<=dvt[dc];i++)
			if(i%np==0) ptr[i]=ptr[i-1];
			else ptr[i]=(LL)ptr[i-1]*i%dvt[dc];
		m[dc]=dvt[dc];M[dc]=P/m[dc];t[dc]=inv(M[dc],m[dc]);
		tM[dc]=(LL)t[dc]*M[dc]%P;
	}
	inline void Init(int x)
	{
		P=x;
		for(int i=2;i*i<=x;i++)
			if(x%i==0) Add(i,x);
		if(x!=1) Add(x,x);
	}
	int Calc(int n,int idx)
	{
		int *ptr=table[idx],v=dv[idx],vt=dvt[idx];
		if(n<v) return ptr[n];
		return (LL)Calc(n/v,idx)*Pow(ptr[vt],n/vt,vt)*ptr[n%vt]%vt;
	}
	int C(int n,int m,int idx)
	{
		int times,v,t,vt;
		v=dv[idx],t=dt[idx],vt=dvt[idx];times=0;
		for(int i=n;i;i/=v) times+=i/v;
		for(int i=m;i;i/=v) times-=i/v;
		for(int i=n-m;i;i/=v) times-=i/v;
		if(times>=t) return 0;
		else
		{
			int pt,fn,fm,fnmm;
			pt=Pow(v,times);
			fn=Calc(n,idx),fm=Calc(m,idx),fnmm=Calc(n-m,idx);
			return (LL)pt*fn*inv(fm,vt)*inv(fnmm,vt)%vt;
		}
	}
	inline int CRT()
	{
		int res=0;
		for(int i=1;i<=dc;i++) res=((LL)A[i]*tM[i]+res)%P;
		return res;
	}
	inline int C(int n,int m)
	{
		if(n<m) return 0;
		for(int i=1;i<=dc;i++) A[i]=C(n,m,i);
		return CRT();
	}
}
int a[MAXN],ac,n,m;
//前ac个数<=a[i] 所有的数>=1的方案数
void WORK()
{
	int n1,n2,t;
	get(n),get(n1),get(n2),get(m);
	for(int i=1;i<=n1;i++) get(a[i]);
	ac=n1;
	for(int i=1;i<=n2;i++) get(t),m-=t-1;
	int sum,cnt,ANS=0,res;
	for(int i=(1<<n1)-1;~i;i--)
	{
		sum=m,cnt=0;
		for(int j=1;j<=ac;j++)
			if(i&(1<<j>>1)) cnt++,sum-=a[j];
		res=iLucas::C(sum-1,n-1);
		if(cnt&1) ANS-=res,((ANS%=P)+=P)%=P;
		else ANS+=res,ANS%=P;
	}
	printf("%d\n",ANS);
}
int main()
{
	int T;get(T),get(P);iLucas::Init(P);
	while(T--) WORK();
	return 0;
}

发表于 | 更新于

Link

好题。 存在一处容易遗漏的细节： 若001∈S001 \in S，11合法。 出题人比较心软只卡了20pts。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=2000+10,P=1e9+7;
//正整数
namespace iAC
{
	const int SIZE=MAXN;
	const char SB='0',SE='9';
	const int SIGMA=SE-SB+1;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;int cnt;
		int g[MAXN][2],f[MAXN];
		Node *&next(char c){return son[c-SB];}
		Node()
		{
			memset(son,0,sizeof(son));fail=last=0;cnt=0;
			memset(g,0,sizeof(g));memset(f,0,sizeof(f));
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*root=new(ME++) Node;
	Node *newNode(){return new(ME++) Node;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	void Build()
	{
		static Node *Q[SIZE];int he=1,ta=0;
		root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node* cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}using namespace iAC;
typedef long long LL;
LL DP(char *N)
{
	LL res=0;int L=strlen(N+1);
	root->f[0]=1;
	for(int i=1;i<L;i++)
		for(Node *ptr=POOL;ptr!=ME;++ptr)
			for(char c=i==1?'1':'0';c<='9';++c)
				if(!ptr->next(c)->cnt && !ptr->next(c)->last)
					(ptr->next(c)->f[i]+=ptr->f[i-1])%=P;
	//res累加f[all][0~L-1]
	root->g[0][0]=1;
	for(int i=1;i<=L;i++)
		for(Node *ptr=POOL;ptr!=ME;++ptr)
			for(char c=i==1?'1':'0';c<='9';++c)
				if(!ptr->next(c)->cnt && !ptr->next(c)->last)
				{
					if(c==N[i])
						(ptr->next(c)->g[i][0]+=ptr->g[i-1][0])%=P;
					else if(c<N[i]) (ptr->next(c)->g[i][1]+=ptr->g[i-1][0])%=P;
					(ptr->next(c)->g[i][1]+=ptr->g[i-1][1])%=P;
				}

	for(Node *ptr=POOL;ptr!=ME;++ptr)
	{
		(res+=ptr->g[L][0]+ptr->g[L][1])%=P;
		for(int i=1;i<L;i++)
			(res+=ptr->f[i])%=P;
	}
	return res;
}
int main()
{
	static char N[MAXN],str[MAXN];
	scanf("%s",N+1);
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		Insert(str);
	}
	Build();
	LL ANS=DP(N);
	printf("%lld\n",ANS);
	return 0;
}
/* AC Record(Bugs) *
 *	WA Naive.Detail ignored. 
 MLE LL Array MAXN to large
 NOT WA BUT next->last!!!
 * * * * * * * * * */

发表于 | 更新于

Cool。。

Link

(权限题。。一开始用小号交的时候显示：Where do find this link?No such problem.我就不说什么了。)

Description

Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。 接下来会发生q个操作，操作有两种形式： “1 P”，Bob往自己的集合里添加了一个字符串P。 “2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的子串） Bob遇到了困难，需要你的帮助。

Solution

嗯。。寻找集合TT中有多少串包含SxS_x，可以用Fail树做。 于是就把询问离线，把S,TS,T的字符串扔到一个Trie里然后跑出来AC自动机。建立了Fail树，对于一个询问xx，就转化为查询Fail树，SxS_x的末尾节点对应节点的子树中，存在多少表示TT中在此查询之前插入的串的节点，可以用线段树维护。 在建立AC自动机的时候，在Trie的每个节点记录有多少串包含了这个节点，O(L)O(L) 然后一遍DFS，加上线段树合并的复杂度，总共是O(Llogn)O(L\log n)。 写完之后交上去居然1A了。。 虽然这么暴力但跑的也不是很慢，11s。重载operator new之后快了1s。。只是内存占用超级大。。500M。。

正解

对SS建立AC自动机，建立Fail树。每个节点维护一个值，记录子树下有多少个T。 对于TT中的新串在AC自动机上跑，记录到达的节点。然后把Fail树中这些节点的值+1，把相邻点的LCA的值-1。查询就是子树和了。Orz。。又快又好写。。

Tips

只想出暴力离线的做法还是因为学得有些死板。一个串在AC自动机上跑到的节点，和在AC自动机上串的节点的性质其实是差不多的。

Code（新代码风格，欢迎拍砖吐槽）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10,SIZE=(2000000+10)<<1;
using std::pair;
using std::make_pair;

namespace iList
{
	template <class T> struct Node
	{
		Node *pre;T val;
		Node(Node *pre,T val):pre(pre),val(val){}
	};//*ME=(Node*)malloc(SIZE*sizeof(Node));
	template <class T> struct List
	{
		Node<T> *head;
		void Add(T v){head=new Node<T>(head,v);}
		void Clear(){head=0;}
	};
	List<int> G[SIZE],strs[SIZE];
	List<pair<int,int> > query[SIZE];
}using namespace iList;

namespace iAC
{
	const char SB='a',SE='z';
	const int SIGMA=SE-SB+1;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;
		int cnt;
		List<int> strs;
		Node *&next(char c){return son[c-SB];}
		Node(){memset(son,0,sizeof(son));fail=last=0;cnt=0;strs.Clear();}
		int num();
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*root=new(ME++) Node;
	Node* newNode(){return new(ME++) Node;}
	int Node::num(){return this-POOL+1;}
	Node* Insert(char *s,int c=0)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
			if(c) cur->strs.Add(c);
		}
		cur->cnt++;
		return cur;
	}
	void Build()
	{
		static Node *Q[SIZE];int he,ta;
		he=1,ta=0;root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}using namespace iAC;
namespace iSeg
{
	const int SIZE=MAXN<<2;
	int TL,TR;
	struct Node
	{
		Node *son[2];
		int v;
		Node(){v=0;}
		void up(){v=son[0]->v+son[1]->v;}
		bool isleaf(){return son[0]==son[1];}
	}*null=new Node,*ME=(Node*)malloc(SIZE*sizeof(Node));
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->v=0;cur->son[0]=cur->son[1]=null;
		cur->up();
		return cur;
	}
	Node *Merge(Node *a,Node *b)
	{
		if(a==null) return b;
		if(b==null) return a;
		assert(a->isleaf()==b->isleaf());
		if(a->isleaf() && b->isleaf())
			a->v=a->v|b->v;	
		else
		{
			Node *lc=Merge(a->son[0],b->son[0]),*rc=Merge(a->son[1],b->son[1]);
			a->son[0]=lc,a->son[1]=rc;a->up();
		}
		return a;
	}
	struct Seg
	{
		Node *root;
		Seg(Node *root=null):root(root){}
		int Access(Node *pos,int L,int R,int l,int r)
		{
			if(pos==null) return 0;
			if(L==l && R==r) return pos->v;
			else
			{
				int MID=(L+R)>>1;
				if(r<=MID) return Access(pos->son[0],L,MID,l,r);
				else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
				else return Access(pos->son[0],L,MID,l,MID)+Access(pos->son[1],MID+1,R,MID+1,r);
			}
		}
		void Edit(Node *&pos,int L,int R,int goal)
		{
			if(pos==null) pos=newNode();
			if(L==R) pos->v=1;
			else
			{
				int MID=(L+R)>>1;
				if(goal<=MID) Edit(pos->son[0],L,MID,goal);
				else Edit(pos->son[1],MID+1,R,goal);
				pos->up();
			}
		}
		void Edit(int pos){Edit(root,TL,TR,pos);}
		int Access(int l,int r){return Access(root,TL,TR,l,r);}
	};
	Seg Merge(Seg a,Seg b){return Seg(Merge(a.root,b.root));}			
}using namespace iSeg;
void InitTree()
{
	for(iAC::Node* ptr=iAC::POOL;ptr!=iAC::ME;++ptr)
	{
		if(ptr->fail!=ptr)//root!!!
			G[ptr->fail->num()].Add(ptr->num());
		strs[ptr->num()]=ptr->strs;
	}
}
int ANS[MAXN];
Seg DFS(int pos)
{
	Seg tree;
	for(iList::Node<int> *ptr=strs[pos].head;ptr;ptr=ptr->pre)
		tree.Edit(ptr->val);
	for(iList::Node<int> *ptr=G[pos].head;ptr;ptr=ptr->pre)
	{
		int u=ptr->val;
		tree=Merge(tree,DFS(u));
	}
	for(iList::Node<pair<int,int> > *ptr=query[pos].head;ptr;ptr=ptr->pre)
		ANS[ptr->val.second]=tree.Access(1,ptr->val.first);
	return tree;
}
int main()
{
	freopen("input","r",stdin);
	static char str[::SIZE];
	static iAC::Node *ref[MAXN];
	int n;get(n);
	for(int i=1;i<=n;i++) scanf("%s",str+1),ref[i]=Insert(str);
	int q,scnt=0;get(q);
	for(int i=1;i<=q;i++)
	{
		int opt,x;get(opt);
		if(opt==1) scanf("%s",str+1),Insert(str,++scnt),ANS[i]=-1;
		else get(x),query[ref[x]->num()].Add(make_pair(scnt,i));
	}
	TL=1,TR=scnt;
	Build();
	InitTree();
	int root=iAC::root->num();
	DFS(root);
	for(int i=1;i<=q;i++)
		if(~ANS[i]) printf("%d\n",ANS[i]);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

发表于 | 更新于

Link

Solution

在每个节点上记录f[i]f[i]表示长度为ii的串匹配到当前节点的最大匹配数，更新后继节点的值即可。

Tips

初始值的设置要仔细考虑。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//Code by Lucida
#include<bits/stdc++.h>
//#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1000+10,INF=0x1f1f1f1f;
using std::fill_n;
namespace AC
{
	const char SB='A',SE='C';
	const int SIGMA=SE-SB+1;
	const int SIZE=20*20;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;
		int cnt,f[MAXN];
		Node *&next(char c){return son[c-SB];}
		Node()
		{
			memset(son,0,sizeof(son));
			fail=last=0;cnt=0;
			fill_n(f,sizeof(f)/sizeof(f[0]),-INF);
		}
	}*root=new Node,*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	Node *newNode(){return new(ME++) Node;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	Node *Q[SIZE];int he,ta;
	void Build()
	{
		he=1,ta=0;	
		root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					if(son->last) son->cnt+=son->last->cnt;
					Q[++ta]=son;
				}
			}
		}
	}
	int DP(int K)
	{
		int res=0;
		root->f[0]=0;
		for(int i=1;i<=K;i++)
		{
			Q[he=ta=1]=root;
			while(he<=ta)
			{
				Node *cur=Q[he++];
				for(char c=SB;c<=SE;++c)
				{
					Node *&son=cur->next(c);
					if(son->f[i]==-INF)
					{
						Q[++ta]=son;
						son->f[i]++;
					}
					chkmx(son->f[i],cur->f[i-1]+son->cnt);
					if(i==K) chkmx(res,son->f[K]);
				}
			}
		}//f[k] f[i]
		return res;
	}
}
using namespace AC;
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n,K;get(n),get(K);
	for(int i=1;i<=n;i++)
		scanf("%s",s+1),Insert(s);
	Build();
	printf("%d\n",DP(K));
	return 0;
}
/* AC Record(Bugs) *
 * RE the -1 at 74 isn't sure to be covered. 
 * * * * * * * * * */