发表于 | 更新于

Link

神校XJ之学霸兮，Dzy皇考曰JC。 摄提贞于孟陬兮，惟庚寅Dzy以降。 纷Dzy既有此内美兮，又重之以修能。 遂降临于OI界，欲以神力而凌辱众生。 今Dzy有一魞歄图，其上有N座祭坛，又有M条膴蠁边。 时而Dzy狂WA而怒发冲冠，神力外溢，遂有K条膴蠁边灰飞烟灭。 而后俟其日A50题则又令其复原。（可视为立即复原） 然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。

Solution

什么鬼！ 求出图的一个生成树。如果割掉一条树边之后想让图不连通，必须割掉所有可以连接树边两端的联通块的回边，称为覆盖着这条树边的边。 然后很神奇地给每个回边随机一个值，那么只要求出所有覆盖某条被删掉的树边的回边的异或和，然后看一下集合中能否异或出来这个值就行了。那就等价于，给每个树边的一个权值，权值为所有覆盖这条树边的回边的异或和，这样只要看删掉的边集的权值是否线性无关。 求树边的权值的过程也很高能 在每个点维护一个值vv，给每条回边随机上一个值之后，用这个值在异或一下回边的两端的点的vv。这样的话，自底向上DFS，一条树边的权值就是树边指向的子树vv的异或和。因为只有一端在这个点下方的回边才会被计算进去，如果起点和终点都在下方，异或两下就没了。

Tips

“异或两下就没了” “随机+异或”做hash

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
#include "lucida"
typedef unsigned long long qword;
using std::fill;
const int MAXN=100000+11,MAXM=500000+11;
struct Edge {
	int to,id;Edge *pre;
	Edge(int to,int id,Edge *pre):to(to),id(id),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int id) {
	G[f]=new Edge(t,id,G[f]);
	G[t]=new Edge(f,id,G[t]);
}
qword ehava[MAXM],phava[MAXN];bool ud[MAXN];
void DFS(int pos,int from) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) {
		if(e->to!=from) {
			int u=e->to;
			if(ud[u]) {
				if(!ehava[e->id]) {
					ehava[e->id]=(qword)rand()<<31|rand();//回边
					phava[pos]^=ehava[e->id];
					phava[u]^=ehava[e->id];
				}
			} else {
				DFS(u,pos);
			}
		}
	}
}
void Calc(int pos) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) {
		int u=e->to;
		if(!ud[u]) {
			Calc(u);
			ehava[e->id]=phava[u];
			phava[pos]^=phava[u];
		}
	}
}
bool Query(int lis[],int n) {
	static qword a[62];
	fill(a,a+62,0);
	for(int i=1;i<=n;++i) {
		qword x=ehava[lis[i]];
		for(int lg=61;~lg;--lg) {
			if(x>>lg&1) {
				if(!a[lg]) {
					a[lg]=x;
					break;
				} else {
					x^=a[lg];			
				}
			}
		}
		if(!x) {
			return 0;
		}
	}
	return 1;
}
int main() {
	//我一定要在八点之前把这道题彻底搞懂并A掉！
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int n,m;is>>n>>m;
	static struct {int x,y;}edges[MAXM];
	for(int i=1;i<=m;++i) {
		is>>edges[i].x>>edges[i].y;
		Adde(edges[i].x,edges[i].y,i);
	}
	fill(ud+1,ud+1+n,0);DFS(1,0);
	fill(ud+1,ud+1+n,0);Calc(1);
	int counter=0;
	#define decode(x) (x^=counter)
	static int cut[20],ec;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		is>>ec;
		for(int j=1;j<=ec;++j) {
			is>>cut[j];
			decode(cut[j]);
		}
		bool Ans=Query(cut,ec);
		counter+=Ans;
		os<<(Ans?"Connected":"Disconnected")<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

好题，只可惜不是原创。

Solution

暴力非常好写，直接模拟，不停地sort，改一改比较的functor，然后就TLE啦！ 很明显那么做完全没有利用到只有一个询问这个条件。 考虑排序有什么意义 从单个元素看，区间[l,r][l,r]第KK小/大恰好在l+K−1l+K-1的位置(废话) 从整体的区间来看，区间[l,p−1][l,p-1]的所有数字都比a[p]a[p]小/大(废话) 第一个性质涉及到单点，似乎没有很大的价值， 相比之下，第二个性质本来就带着“区间”，似乎可以试试。 根据第二个性质，似乎套个二分答案就可以把区间的数字都变成0/10/1了？于是正解就出来了 当然作为一个juruo以上纯属看题解之后的表演

Why Can't

没有对单个数字的条件充分思考下去，而且抱着第一个性质不放，没有把思维发散出去。

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
#include "lucida"
#define pass void(0)

const int MAXN=1e5+11;
namespace segtree {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		int cnt,sz,cov;
		Node():cnt(0),sz(1),cov(-1) {}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
		void Cover(int c) {
			cnt=sz*c;
			cov=c;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
		void Down() {
			if(cov!=-1) {
				son[0]->Cover(cov);
				son[1]->Cover(cov);
				cov=-1;
			}
		}
	};
	struct SegTree {
		Node *root;int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node;
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
				pos->sz=pos->son[0]->sz+pos->son[1]->sz;
			}
		}
		int Access(Node *pos,int L,int R,const int l,const int r) {
			if(l<=L && R<=r) return pos->cnt;
			else {
				int Mid=(L+R)>>1;pos->Down();
				return (l<=Mid?Access(pos->son[0],L,Mid,l,r):0)+(Mid+1<=r?Access(pos->son[1],Mid+1,R,l,r):0); 
			}
		}
		void Edit(Node *pos,int L,int R,const int l,const int r,const int c) {
			if(l<=L && R<=r) pos->Cover(c);
			else {
				int Mid=(L+R)>>1;pos->Down();
				l<=Mid?Edit(pos->son[0],L,Mid,l,r,c):pass;
				Mid+1<=r?Edit(pos->son[1],Mid+1,R,l,r,c):pass;
				pos->Up();
			}
		}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Reset() {
			root->Cover(0);
		}
		int Access(int l,int r=0) {
			return l<=(r?r:l)?Access(root,L,R,l,r?r:l):0;
		}
		void Edit(int l,int r,int c) {
			l<=r?Edit(root,L,R,l,r,c):pass;
		}
		void Edit(int pos,int c) {
			Edit(root,L,R,pos,pos,c);
		}
	};
}using segtree::SegTree;
int n,m,q,a[MAXN];
struct Opt {
	int op,l,r;
}op[MAXN];
bool MaybeSmaller(int x) {
	static SegTree seg(1,n);
	seg.Reset();
	for(int i=1;i<=n;++i) {
		seg.Edit(i,x<a[i]);
	}
	//<= : 0  > : 1
	for(int i=1;i<=m;++i) {
		int sum=seg.Access(op[i].l,op[i].r);
		if(op[i].op==0) {
			seg.Edit(op[i].l,op[i].r-sum,0);
			seg.Edit(op[i].r-sum+1,op[i].r,1);
		} else {
			seg.Edit(op[i].l,op[i].l+sum-1,1);
			seg.Edit(op[i].l+sum,op[i].r,0);
		}
	}
	return seg.Access(q)==0;
}
int main() {
	freopen("input","r",stdin);
	is>>n>>m;
	for(int i=1;i<=n;++i) {
		is>>a[i];
	}
	for(int i=1;i<=m;++i) {
		is>>op[i].op>>op[i].l>>op[i].r;
	}
	is>>q;
	int L=1,R=n;
	while(L!=R) {
		int Mid=(L+R)>>1;
		MaybeSmaller(Mid)?(R=Mid):(L=Mid+1);
	}
	os<<L<<'\n';
	return 0;
}

发表于 | 更新于

Link

标解是NOI式的一本正经 然而有POI式的闹着玩的做法

Solution

首先要读懂题目。。。 kk项指的是可以重复的项，也就是kk个质数相乘。。。。所以最大的项肯定就是形如pdp^d的数字了。。。 然后就要考虑采取POI式的堆+扩展法 表示数字为numnum，最大项为largelarge，最大项的个数为ltlt，还可以继续扩展的最大的数字为lastlast。 初始状态就把128128以内的单个质数的≤N\le N的幂全都弄到堆里面，然后弹KK次。如果堆顶的数字largelarge因子个数不为11，那就把堆顶数字的一个largelarge因子依次替换成prime[1:last]prime[1:last]的一个数字。 对于任意一个伪光滑数，可以把其中的因子从小到大依次替换，只会得到一条到初始状态的路径。

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
#include "lucida"
using std::priority_queue;
struct Node {
	int64 num;
	int large,lt,last;
	Node(int64 num,int large,int lt,int last):num(num),large(large),lt(lt),last(last) {}
	bool operator <(const Node &a) const {
		return num<a.num;
	}
};
int main() {
	freopen("input","r",stdin);
	int64 N;int K;is>>N>>K;
	static int prime[200],pcnt;
	priority_queue<Node> Q;
	for(int i=2;i<=128;++i) {
		static bool nope[200];
		if(!nope[i]) {
			prime[++pcnt]=i;
			int64 x=i,endx=N-N%i;
			for(int j=1;x<=endx;++j,x*=i)
				Q.push(Node(x,i,j,pcnt-1));
		}
		for(int j=1;j<=pcnt && i*prime[j]<=128;++j) {
			nope[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<=K-1;++i) {
		Node top=Q.top();Q.pop();
		if(top.lt!=1)
			for(int j=1;j<=top.last;++j)
				Q.push(Node(top.num/top.large*prime[j],top.large,top.lt-1,j));
	}
	int64 Ans=Q.top().num;
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

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
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
#include "lucida"
using std::fill;
using std::copy;
const int MAXN=50+5,MAXP=5000+11,MAXM=(MAXP<<1)+MAXP,INF=0x1f1f1f1f;
const char BLANK='*',SOFT='x',HARD='#';
struct Edge {
	int to,cap,v;Edge *pre,*rev;
	Edge(int to,int cap,Edge *pre):to(to),cap(cap),v(0),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXP];
void Adde(int f,int t,int cap) {
	G[f]=new Edge(t,cap,G[f]);
	G[t]=new Edge(f,0,G[t]);//cap????
	G[f]->rev=G[t];
	G[t]->rev=G[f];
}
namespace isap {
	const int MAXN=MAXP;
	int s,t,n,d[MAXN],num[MAXN];
	Edge *arc[MAXN],*pe[MAXN];
	int Aug() {
		int minf=INF;
		for(Edge *e=pe[t];e;e=pe[e->rev->to]) {
			chkmn(minf,e->cap-e->v);
		}
		for(Edge *e=pe[t];e;e=pe[e->rev->to]) {
			e->v+=minf;
			e->rev->v-=minf;
		}
		return minf;
	}
	bool Advanced(int &cp) {
		for(Edge *&e=arc[cp];e;e=e->pre) {
			if(e->cap>e->v && d[cp]==d[e->to]+1) {
				pe[cp=e->to]=e;
				return 1;
			}
		}
		return 0;
	}
	int ISAP() {
		fill(d+s,d+t+1,0);
		fill(num,num+1+n,0);
		copy(G+s,G+t+1,arc+s);
		num[0]=n;int flow=0;pe[s]=0;
		for(int cp=s;d[s]<n;cp=cp==t?(flow+=Aug(),s):cp) {
			if(!Advanced(cp)) {
				if(!--num[d[cp]]) {
					break;
				}
				d[cp]=n;
				for(Edge *e=(arc[cp]=G[cp]);e;e=e->pre) {
					if(e->cap>e->v) {
						chkmn(d[cp],d[e->to]+1);
					}
				}
				cp=cp==s?cp:pe[cp]->rev->to;
			}
		}
		return flow;
	}
}using isap::ISAP;
int main() {
	freopen("input","r",stdin);
	//先搜出经过每个点的所有横长条和竖长条
	//一个横长条只能配一个竖长条
	static char map[MAXN][MAXN];
	static int xi[MAXN][MAXN],yi[MAXN][MAXN];
	int xic=0,yic=0,n,m;
	is>>n>>m;
	for(int x=1;x<=n;++x) {
		is>>(map[x]+1);//map[x]..
	}
	for(int x=1;x<=n;++x) {
		map[x][0]=map[x][m+1]=HARD;
	}
	for(int y=1;y<=m;++y) {
		map[0][y]=map[n+1][y]=HARD;
	}
	for(int x=1;x<=n;++x) {
		for(int y=1;y<=m;++y) {
			if(map[x][y]==HARD) {
				continue;
			}
			if(!xi[x][y]) {
				++xic;
				for(int k=x;map[k][y]!=HARD;++k) {
					xi[k][y]=xic;
				}
			}
			if(!yi[x][y]) {
				++yic;
				for(int k=y;map[x][k]!=HARD;++k) {
					yi[x][k]=yic;
				}
			}
		}
	}
	isap::s=0;isap::t=xic+yic+1;isap::n=isap::t+1;
	for(int i=1;i<=xic;++i) {
		Adde(isap::s,i,1);
	}
	for(int i=1;i<=yic;++i) {
		Adde(i+xic,isap::t,1);
	}
	for(int x=1;x<=n;++x) {
		for(int y=1;y<=m;++y) {
			if(map[x][y]==BLANK) {
				Adde(xi[x][y],yi[x][y]+xic,1);
			}
		}
	}
	int Ans=ISAP();
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "lucida"
using std::pair;
using std::swap;
/*int64 mul(int64 x,int64 times,int64 modu) {
	if(x<times) swap(x,times);
	int64 res;
	for(res=0;times;(x+=x)%=modu,times>>=1)
		if(times&1) (res+=x)%=modu;
	return res;
}*/
int64 mul(int64 a,int64 b,int64 modu)
{
    int64 temp=a*b-(int64)((long double)a/modu*b+1e-8)*modu;
    if (temp<0) temp+=modu;
    return temp;
}
int64 pow(int64 base,int64 index,int64 modu) {
	int64 res;
	for(res=1;index;base=mul(base,base,modu),index>>=1)
		if(index&1) res=mul(res,base,modu);
	return res;
}
int64 exgcd(int64 a,int64 b,int64 &x,int64 &y) {
	if(!b) {
		x=1,y=0;
		return a;
	} else {
		int64 d=exgcd(b,a%b,x,y);
		swap(x,y);y-=(a/b)*x;
		return d;
	}
}
int64 gcd(int64 a,int64 b) {
	a=a<0?-a:a;b=b<0?-b:b;
	for(int64 t;b;t=a%b,a=b,b=t);
	return a;
}
int64 FindDivisor(int64 x) {
	int64 c=rand()%(x-1)+1,d;
	for(int64 p2=rand()%x,p1=(mul(p2,p2,x)+c)%x,s=1,k=2;(d=gcd(p1-p2,x))==1;p1=(mul(p1,p1,x)+c)%x,++s)
		if(s==k) {
			p2=p1;
			k<<=1;
		}
	return d;
}
pair<int64,int64> Divide(int64 x) {
	int64 res;
	while((res=FindDivisor(x))==x);
	return pair<int64,int64>(res,x/res);
}
int main() {
	freopen("input","r",stdin);
	int64 e,N,c;is>>e>>N>>c;
	pair<int64,int64> pq=Divide(N);
	int64 r=(pq.first-1)*(pq.second-1);
	int64 x,y,gcd=exgcd(e,r,x,y);
	assert(gcd==1);
	int64 d=(x%r+r)%r,n=pow(c,d,N);
	os<<d<<' '<<n<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

从高位到低位DP f[i][x][0/1][0/1][0/1][0/1][0/(1,2)]f[i][x][0/1][0/1][0/1][0/1][0/(1,2)] 表示第ii位为xx，卡不卡下界，卡不卡上界，有无44，有无88，有重复33次的了/最后一位已经重复了1/21/2次

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
#include "lucida"
void Divide(int64 x,int bit[],int &n) {
	for(n=0;x;x/=10) bit[++n]=x%10;
}
int main() {
	freopen("input","r",stdin);
	static int lb[20],rb[20],ln,rn;
	static int64 f[12][10]  [2][2]    [2][2]          [3];
	//第[]位，为[]，卡/不卡下[]/上[] 是否有4[]/8[]	0:有3位了 1/2:已经重复了1/2次[]
	int64 L,R;is>>L>>R;
	Divide(L,lb,ln);
	Divide(R,rb,rn);
	for(int x=0;x<10;++x)
		f[11][x][x==lb[11]][x==rb[11]][x==4][x==8][1]=lb[11]<=x && x<=rb[11];
	for(int i=10;i;--i) {
		for(int cx=0;cx<10;++cx) {
			for(int px=0;px<10;++px) {
				for(int pl=0;pl<2;++pl) {
					for(int pr=0;pr<2;++pr) {
						for(int p4=0;p4<2;++p4) {
							for(int p8=0;p8<2;++p8) {
								for(int p3=0;p3<3;++p3) {
									if((pl && cx<lb[i]) || (pr && cx>rb[i]) || (p4 && p8)) continue;
									f[i][cx][pl && cx==lb[i]][pr && cx==rb[i]][p4 || cx==4][p8 || cx==8][!p3?0:(cx==px?(p3+1)%3:1)]+=f[i+1][px][pl][pr][p4][p8][p3];
								}
							}
						}
					}
				}
			}
		}
	}
	int64 Ans=0;
	for(int x=0;x<10;++x) {
		for(int cl=0;cl<2;++cl) {
			for(int cr=0;cr<2;++cr) {
				for(int c4=0;c4<2;++c4) {
					for(int c8=0;c8<2;++c8) {
						Ans+=(!c4 || !c8)*f[1][x][cl][cr][c4][c8][0];
					}
				}
			}
		}
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

留一个KDTree模板。。 另外，如果要强转int64，需要在每个优先级相同的并列的表达式里面都强转 比如 

1
int64 res=a*x+b*y

必须写成 

1
int64 res=(int64)a*x+(int64)b*y

居然被这种问题坑了。

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
#include "lucida"
using std::max;
using std::min;
using std::pair;
using std::nth_element;
const int MAXN=50000+11,INF=2e9;
struct point {
	int x[2];
	point() {}
	point(int x0,int x1) {
		x[0]=x0;
		x[1]=x1;
	}
	int64 inner(int64 a,int64 b) {
		return a*x[0]+b*x[1];
	}
	int &operator [](int d) {
		return x[d];
	}
	const int &operator [](int d) const{
		return x[d];
	}
};
struct cmp {
	int d;
	cmp(int d):d(d) {}
	template <class T> 
	bool operator () (const pair<point,T> &a,const pair<point,T> &b) {
		return a.first[d]<b.first[d];
	}
};
namespace kdtree {
	struct Node *null;
	//0 min 1 mx
	struct Node {
		Node *son[2];
		point p,m[2];
		int64 val,sumv;
		Node():sumv(0) {
			m[0]=point(INF,INF);
			m[1]=point(-INF,-INF);
			son[0]=son[1]=0;
		}
		Node(point p,int64 val):p(p),val(val),sumv(val) {
			m[0]=m[1]=p;
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN);
			return Me++;
		}
		void Up() {
			for(int d=0;d<2;++d) {
				chkmn(m[0][d]=p[d],min(son[0]->m[0][d],son[1]->m[0][d]));
				chkmx(m[1][d]=p[d],max(son[0]->m[1][d],son[1]->m[1][d]));
			}
			sumv=val+son[0]->sumv+son[1]->sumv;
		}
		int64 PoMin(int64 a,int64 b) {
			int64 res=LLONG_MAX;
			for(int s0=0;s0<2;++s0)
				for(int s1=0;s1<2;++s1)
					chkmn(res,a*m[s0][0]+b*m[s1][1]);
			return res;
		}
		int64 PoMax(int64 a,int64 b) {
			int64 res=LLONG_MIN;
			for(int s0=0;s0<2;++s0)
				for(int s1=0;s1<2;++s1)
					chkmx(res,a*m[s0][0]+b*m[s1][1]);
			return res;
		}
	}*_null=null=new Node;
	//查询所有满足ax+by<c 的点权和
	struct KDTree {
		Node *root;
		void Build(Node *&pos,int L,int R,pair<point,int64> p[],int d) {
			if(L>R) return;
			int Mid=(L+R)>>1;
			nth_element(p+L,p+Mid,p+R+1,cmp(d));
			pos=new Node(p[Mid].first,p[Mid].second);
			if(L!=R) {
				Build(pos->son[0],L,Mid-1,p,d^1);
				Build(pos->son[1],Mid+1,R,p,d^1);
				pos->Up();
			}
		}
		KDTree(pair<point,int64> p[],int n) {
			Build(root,1,n,p,0);
		}
		int64 Query(Node *&pos,int a,int b,int64 c) {
			if(!pos) return 0;
			int64 pmn=pos->PoMin(a,b),pmx=pos->PoMax(a,b);
			if(pmx<c) return pos->sumv;
			else if(pmn>=c) return 0;
			else return Query(pos->son[0],a,b,c)+pos->val*(pos->p.inner(a,b)<c)+Query(pos->son[1],a,b,c);
		}
		int64 Query(int a,int b,int64 c) {
			return Query(root,a,b,c);
		}
	};
}using kdtree::KDTree;
int main() {
	freopen("input","r",stdin);
	static pair<point,int64> ch[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i)
		is>>ch[i].first[0]>>ch[i].first[1]>>ch[i].second;
	KDTree kdt(ch,n);
	for(int i=1;i<=m;++i) {
		int a,b;int64 c;is>>a>>b>>c;
		int64 Ans=kdt.Query(a,b,c);
		os<<Ans<<'\n';
	}
	return 0;
}

发表于 | 更新于

Problem

质因子分解一个给定的很大的NN

Solution

Part I:质数判定 Miller-Rabin算法

费马小定理

，逆定理成立的概率也很大。 如果任意选择一个数字a0a_0，发现 ，那么PP就有很大概率是个质数。如果随机地多取几个a0a_0，那么出错的概率会大大减小。 但是仍然有一些合数XX，满足对于 。这些数字成为Carmichael数。为了把这些数字也正确地判断掉，引入了

二次探测定理

PP是一个质数，那么 的解 。 也就是说如果 且 ，那么XX不是质数。

做法

所以就随机选几个数字a[]a[]，用费马小定理结合二次探测定理来测试一下。 具体的做法，就是提取P−1P-1中的22，把P−1P-1化为 的形式 求出ada^d，一路平方，如果出现了 而 ，就不是质数。 最后会得到aP−1a^{P-1}，再看看这个是不是=1=1。

Part II:寻找因子 Pollard-Rho算法

寻找因子，试除法的复杂度是O(N)O(\sqrt N)的，处理不了64位整数的范围。 于是Pollard-Rho诞生了

生日悖论

从[1,N][1,N]里面选两个数，两个数字相等的概率是1N2\dfrac 1{N^2} 但如果从[1,N][1,N]里面选三个数，使得前两个数字的差等于第三个数，那么概率就能增加不少，因为每个数对应着两个和它差值为一个定值的数。 如果选的更多，那么概率就更大。用一个通俗的模型解释，就是在≥23\ge 23人中，有>50%> 50\%的概率出现两个人生日在同一天，然后这似乎并不符合常理，所以就是生日悖论。

Pollard-Rho

提到了生日悖论，多半是要用基于概率的算法了。。大体的做法就是遍历一个随机数序列，看相邻两项的差与给定xx是否互质，如果不互质，就找到了一个因数。 因为随机数序列存不下，那就一项一项地生成，但是随机数序列会有周期，会卡在里面出不来。 而由于空间限制，判周期只能用Floyd套圈法，那就稍微改变一下策略，让两个指针在随机数序列上分别一次走一步、走两步，直到差与xx不互质。(注：gcd(0,x)==x\gcd(0,x)==x) 在实现的时候，有一个优化。两个指针同时走，会重复地计算很多个项。那么只让一个指针走，另一个指针在它走了2k2^k步之后一步走过去。具体见代码。这个优化的正确性应该比较显然，但是还没有细想会不会产生一些退化的情况。

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
#include "lucida"
const int prime[]={2,3,5,7,11,13,17,19,23,29},C_MAX=99929;
using std::swap;
using std::max;
/*
int64 mul(int64 x,int64 times,int64 modu) {
	if(x<times) swap(x,times);
	int64 res;
	for(res=0;times;(x+=x)%=modu,times>>=1)
		if(times&1) (res+=x)%=modu;
	return res;
}
*/
int64 mul(int64 a,int64 b,int64 modu)
{
    int64 temp=a*b-(int64)((long double)a/modu*b+1e-8)*modu;
    if (temp<0) temp+=modu;
    return temp;
}

int64 pow(int64 base,int64 index,int64 modu) {
	int64 res;
	for(res=1;index;base=mul(base,base,modu),index>>=1)
		if(index&1) res=mul(res,base,modu);
	return res;
}
int64 gcd(int64 a,int64 b) {
	a=a<0?-a:a;b=b<0?-b:b;
	for(int64 t;b;t=a%b,a=b,b=t);
	return a;
}
bool isPrime(int64 x) {
	if(x==2) return 1;
	if(x<2 || ~x&1) return 0;
	int64 s,d;
	for(d=x-1,s=0;~d&1;s++,d>>=1);
	for(int i=0;i<9;++i) {
		if(x==prime[i]) 
			return 1;
		int64 cur=pow(prime[i],d,x);
		if(cur==1 || cur==x-1) continue;
		int64 pre=cur;
		for(int k=1;k<=s;++k) {
			cur=mul(cur,cur,x);
			if(cur==1 && pre!=1 && pre!=x-1) 
				return 0;
			pre=cur;
		}
		if(pre!=1) 
			return 0;
	}
	return 1;
}
int64 FindDivisor(int64 x) {
	int64 c=rand()%C_MAX,d;
	for(int64 p2=rand()%x,p1=(mul(p2,p2,x)+c)%x,k=2,s=1;(d=gcd(p1-p2,x))==1;++s,p1=(mul(p1,p1,x)+c)%x)
		if(k==s) {
			p2=p1;
			k<<=1;
		}
	return d;
}
int64 Solve(int64 x) {
	//os<<x<<'\n';
	if(isPrime(x)) return x;
	int64 r;while((r=FindDivisor(x))==x);
	return max(Solve(r),Solve(x/r));
}
void Work() {
	int64 x;is>>x;
	int64 pd=Solve(x);
	if(pd==x) os<<"Prime"<<'\n';
	else os<<pd<<'\n';
}
int main() {
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int T;is>>T;
	while(T--)
		Work();
	return 0;
}

发表于 | 更新于

Link

真的是很不错的题目..

Solution

借鉴虚树和树分块的思想，尽量减少新树的点数，把一块看成一个整体，在新树中只记录一块的根节点。 需要把一个子树连到大树的点pp上，用二分查找找到pp所在的块，然后用主席树算出pp在原树对应的节点编号。 查询的时候，求出两个点所在块的 ，让这两个点分别跳到处于 块里面的最深的祖先(自身也算)并记录路径长度，再在块内求一个 ，算一下路径长度就好了。

Tips

有一个构造函数的一个int64变量写成了int，怎么也搞不出来。 对拍的时候，确实造了每次+n+n的极限数据，但是查询是随机的，所以没有让这个问题暴露出来。 so，极限数据要在每个方面都极限。。

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
#include "lucida"
using std::lower_bound;
using std::swap;
const int MAXN=100000+11,MAXLOG=20;
int n,log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i)
		log_2[i]=log_2[i>>1]+1;
}}Auto;
struct Edge {
	int to;int64 v;Edge *pre;
	Edge(int to,int64 v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<2);
		return Me++;
	}
};
namespace segtree {
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node():cnt(0) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN*MAXLOG);
			return Me++;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
	}*_null=null=new Node,*_null_son=null->son[0]=null->son[1]=null;
	struct SegTree {
		Node **root;int L,R;
		void Build(Node *&pos,int L,int R,int goal) {
			pos=new Node(*pos);
			if(L==R) pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Build(pos->son[0],L,Mid,goal);
				else Build(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
		int Kiss(Node *pl,Node *pr,int L,int R,int K) {
			if(L==R) return L;
			else {
				int Mid=(L+R)>>1,sz=pr->son[0]->cnt-pl->son[0]->cnt;
				return K<=sz?Kiss(pl->son[0],pr->son[0],L,Mid,K):Kiss(pl->son[1],pr->son[1],Mid+1,R,K-sz);
			}
		}
		SegTree(){}SegTree(int a[],int n):root(alloc(Node*,n+1)),L(1),R(n) {
			root[0]=null;
			for(int i=1;i<=n;++i)
				Build(root[i]=root[i-1],L,R,a[i]);
		}
		int Kiss(int l,int r,int K) {
			return Kiss(root[l-1],root[r],L,R,K);
		}
	};
}using segtree::SegTree;
struct Graph {
	Edge *G[MAXN];
	Graph() {
		dep[1]=1;
	}
	void Adde(const int &f,const int &t,const int64 &v) {
		G[f]=new Edge(t,v,G[f]);
		G[t]=new Edge(f,v,G[t]);
	}
	void operator () (const int &f,const int &t,const int64 &v) {
		Adde(f,t,v);
	}
	Edge *operator [](const int &x) {
		return G[x];
	}
	int par[MAXN][MAXLOG],fa[MAXN],sz[MAXN],dep[MAXN],dfs[MAXN],lbd[MAXN],rbd[MAXN],dc;
	int64 len[MAXN];//dep深度 len距离
	int LCA(int p1,int p2) {
		if(dep[p1]<dep[p2]) swap(p1,p2);
		for(int lg=log_2[dep[p1]-dep[p2]];~lg;--lg)
			p1=dep[par[p1][lg]]>=dep[p2]?par[p1][lg]:p1;
		if(p1==p2) return p1;
		for(int lg=log_2[dep[p1]];~lg;--lg)
			if(par[p1][lg]!=par[p2][lg])
				p1=par[p1][lg],p2=par[p2][lg];
		assert(fa[p1]);
		return fa[p1];
	}
	void DFS(int pos=1) {
		par[pos][0]=fa[pos];
		for(int lg=1;lg<=log_2[dep[pos]];++lg)
			par[pos][lg]=par[par[pos][lg-1]][lg-1];
		dfs[++dc]=pos;
		lbd[pos]=dc;
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa[pos]) {
				int u=e->to;
				fa[u]=pos;
				dep[u]=dep[pos]+1;
				len[u]=len[pos]+e->v;
				DFS(u);
				sz[pos]+=sz[u];
			}
		rbd[pos]=dc;
	}
	int64 Len(int bot,int top) {
		return len[bot]-len[top];
	}
};
struct OriginGraph : Graph{
	SegTree seg;
	void Build() {
		DFS(1);
		new(&seg) SegTree(dfs,dc);
	}
	int KthNode(int rt,int K) {
		return seg.Kiss(lbd[rt],rbd[rt],K);
	}
	int Dist(int p1,int p2) {
		int lca=LCA(p1,p2);
		return len[p1]+len[p2]-len[lca]*2;
	}
}oi;
struct NewGraph : Graph{
	struct Block {
		int64 last,rFa;int vRt;
		Block(){}
		Block(const int64 &last,const int64 &rFa,const int &vRt):last(last),rFa(rFa),vRt(vRt) {} //int rFa??
		bool operator <(const Block &a) const {
			return last<a.last;
		}
	}np[MAXN];int nc;
	struct Point {//Point Info
		int bNum,vRef;
		//block Number
		//virtual Reference in original Tree
		Point(const int &bNum,const int &vRef):bNum(bNum),vRef(vRef) {}
	};
	void Set(const int &n) {
		np[nc=1]=Block(n,0,1);
	}
	Point Ident(const int64 &pos) {
		int bNum=lower_bound(np+1,np+1+nc,Block(pos,0,0))-np,
			vRef=oi.KthNode(np[bNum].vRt,pos-np[bNum-1].last);
		return Point(bNum,vRef);
	}
	void Join(int rt,int64 goal) {
		++nc;np[nc]=Block(np[nc-1].last+oi.sz[rt],goal,rt);
		Point go=Ident(goal);
		Adde(nc,go.bNum,oi.Len(go.vRef,np[go.bNum].vRt)+1);
	}
	int64 JumpTo(int64 &pos,Point &pi,int bgo) {//跳到它上面的bgo块中的最深节点，并计算距离
		if(pi.bNum==bgo)
			return 0;
		else {
			int64 res=oi.Len(pi.vRef,np[pi.bNum].vRt);int b=pi.bNum;
			for(int lg=log_2[dep[b]];~lg;--lg)
				if(dep[par[b][lg]]>dep[bgo]) {
					b=par[b][lg];
				}
			res+=Len(pi.bNum,b)+1;
			pos=np[b].rFa;pi=Ident(pos);
			return res;
		}
	}
	int64 Dist(int64 p1,int64 p2) {
		Point t1=Ident(p1),t2=Ident(p2);
		int blca=LCA(t1.bNum,t2.bNum);
		int64 res=JumpTo(p1,t1,blca)+JumpTo(p2,t2,blca);
		res+=oi.Dist(t1.vRef,t2.vRef);
		return res;
	}
}nw;

int main() {
	freopen("input","r",stdin);
	int m,Q;is>>n>>m>>Q;
	for(int i=1;i<=n-1;++i) {
		int f,t;is>>f>>t;
		oi(f,t,1);
	}
	oi.Build();nw.Set(n);
	for(int i=1;i<=m;++i) {
		int x;int64 to;is>>x>>to;
		nw.Join(x,to);
	}
	nw.DFS();
	for(int i=1;i<=Q;++i) {
		int64 x,y;is>>x>>y;
		int64 Ans=nw.Dist(x,y);
		os<<Ans<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

如果上式==0==0，那么可以得到 也==0==0。 这样的话当 的时候，反推，用后缀的差是否为零来判断s[l:r]s[l:r]是否 剩下的特殊处理就好了

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
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=100000+11;
int n,bn[MAXN],m;
int64 Ans[MAXN],P;
char S[MAXN];	
struct Opt {
	int l,r,id;
	bool operator <(const Opt &x) const {
		return bn[l]!=bn[x.l]?bn[l]<bn[x.l]:r<x.r;
	}
}p[MAXN];
namespace Mo {
	int64 cAns;
	int cnt[MAXN],c[MAXN];
	int64 suf[MAXN],nums[MAXN];
	int64 C2(int n) {
		return n<2?0:(int64)n*(n-1)>>1;
	}
	void Modify(int pos,int d) {
		cAns-=C2(cnt[c[pos]]);
		cnt[c[pos]]+=d;
		cAns+=C2(cnt[c[pos]]);
	}
	void Solve() {
		int bsz=sqrt(n+0.5);
		for(int i=1;i<=n;++i)
			bn[i]=(i-1)/bsz+1;
		int nc=0;
		for(int i=n,pw=1;i;--i,pw=(int64)pw*10%P) {
			suf[i]=((int64)(S[i]-'0')*pw+suf[i+1])%P;
			nums[++nc]=suf[i];
		}
		nums[++nc]=0;sort(nums+1,nums+1+nc);
		nc=unique(nums+1,nums+1+nc)-nums-1;
		for(int i=1;i<=n+1;++i) c[i]=lower_bound(nums+1,nums+1+nc,suf[i])-nums;
		sort(p+1,p+1+m);
		for(int i=1;i<=m;++i) ++p[i].r;
		//区间内有多少种同颜色的点
		for(int i=p[1].l;i<=p[1].r;++i)
			Modify(i,1);
		Ans[p[1].id]=cAns;
		for(int i=2;i<=m;++i) {
			for(int t=p[i-1].l-1;t>=p[i].l;--t) Modify(t,1);
			for(int t=p[i-1].r+1;t<=p[i].r;++t) Modify(t,1);
			for(int t=p[i-1].l;t<=p[i].l-1;++t) Modify(t,-1);
			for(int t=p[i-1].r;t>=p[i].r+1;--t) Modify(t,-1);
			Ans[p[i].id]=cAns;
		}
	}
}
namespace Sp {
	int cnt[MAXN];
	int64 sum[MAXN];
	void Solve() {
		for(int i=1;i<=n;++i) {
			cnt[i]=cnt[i-1]+((S[i]-'0')%P==0);
			sum[i]=sum[i-1]+((S[i]-'0')%P==0)*i;//(i-1)??
		}
		for(int i=1;i<=m;++i)
			Ans[i]=(sum[p[i].r]-sum[p[i].l-1])-(int64)(cnt[p[i].r]-cnt[p[i].l-1])*(p[i].l-1);
	}
}
int main() {
	freopen("input","r",stdin);
	is>>P>>(S+1)>>m;n=strlen(S+1);
	for(int i=1;i<=m;++i) {
		is>>p[i].l>>p[i].r;
		p[i].id=i;
	}
	if(10%P) Mo::Solve(); 
	else Sp::Solve();
	for(int i=1;i<=m;++i)
		os<<Ans[i]<<'\n';
	return 0;
}