shared_ptr(引用计数)模板

发表于 2017-06-27 | 更新于 2018-06-18

好东西啊！！不能用C++11，自己写一个shared_ptr也很简单！！

template <class T>
struct shared_ptr {
public:
	shared_ptr():ptr(0),cnt(0) {}
	shared_ptr(T *p):ptr(0) { *this=p; }
	shared_ptr(shared_ptr const &other):ptr(0) { *this=other; }
	~shared_ptr() { release(); }
	T *operator ->() { return ptr; }
	const T *operator ->() const { return ptr; }
	T &operator *() { return *ptr; }
	T const &operator *() const { return *ptr; }
	operator bool() const { return ptr; }
	shared_ptr &operator =(T *p) {
		release();
		if(p) {
			ptr=p;
			(*(cnt=new int))=1;
		} else {
			ptr=0;
			cnt=0;
		}
		return *this;
	}
	shared_ptr &operator =(shared_ptr const &other) {
		release();
		if(other.ptr) {
			ptr=other.ptr;
			(*(cnt=other.cnt))++;
		} else {
			ptr=0;
			cnt=0;
		}
		return *this;
	}
private:
	T *ptr;
	int *cnt;
	void release() {
		if(ptr && --*cnt==0) {
			delete ptr;
			delete cnt;
		}
	}
};

套上可持久化Treap

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
#define get() is
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1e5+11,MAXNODE=1e6;
template <class T>
struct MemPool {
	T *Me,**rec;
	MemPool(int SIZE):Me((T*)malloc(SIZE*sizeof(T))),rec((T**)malloc(SIZE*sizeof(T*))) { *rec=0; }
	T *Alloc() { return *rec?*rec--:Me++; }
	void Recycle(T *p) { *++rec=p; }
};
template <class T>
struct shared_ptr {
public:
	shared_ptr():ptr(0),cnt(0) {}
	shared_ptr(T *p):ptr(0) { *this=p; }
	shared_ptr(shared_ptr const &other):ptr(0) { *this=other; }
	~shared_ptr() { release(); }
	T *operator ->() { return ptr; }
	const T *operator ->() const { return ptr; }
	T &operator *() { return *ptr; }
	T const &operator *() const { return *ptr; }
	operator bool() const { return ptr; }
	shared_ptr &operator =(T *p) {
		release();
		if(p) {
			ptr=p;
			(*(cnt=Pool.Alloc()))=1;
		} else {
			ptr=0;
			cnt=0;
		}
		return *this;
	}
	shared_ptr &operator =(shared_ptr const &other) {
		release();
		if(other.ptr) {
			ptr=other.ptr;
			(*(cnt=other.cnt))++;
		} else {
			ptr=0;
			cnt=0;
		}
		return *this;
	}
private:
	T *ptr;
	int *cnt;
	static MemPool<int> Pool;
	void release() {
		if(ptr && --*cnt==0) {
			delete ptr;
			Pool.Recycle(cnt);
		}
	}
};
template <class T> 
MemPool<int> shared_ptr<T>::Pool(MAXNODE);
struct Treap {
	int64 Sum(int l,int r) {
		return Split(l,r).second->sumv;
	}
	void Add(int l,int r,int x) {
		Triple sp=Split(l,r);
		sp.second->Add(x);
		root=Merge(sp);
	}
	void Replace(int l,int cnt,int r) {
		ptr_t rt=Split(l,l+cnt-1).second;
		Triple sp=Split(r,r+cnt-1);
		sp.second=rt;
		root=Merge(sp);
	}
	struct Node {
		typedef shared_ptr<Node> ptr_t;
		ptr_t son[2];
		int64 sumv;
		int val,add,size;
		Node(int val):sumv(val),val(val),add(0),size(1) {}
		Node(Node const &other):sumv(other.sumv),val(other.val),add(other.add),size(other.size) {
			son[0]=other.son[0];
			son[1]=other.son[1];
		}
		void *operator new(size_t) {
			return Pool.Alloc();
		}
		void operator delete(void *p) {
			Pool.Recycle((Node*)p);
		}
		void Add(int d) {//add..!!!
			add+=d;
			val+=d;
			sumv+=(int64)d*size;
		}
		void Down() {
			if(add) {
				if(son[0]) {
					son[0]=new Node(*son[0]);
					son[0]->Add(add);
				}
				if(son[1]) {
					son[1]=new Node(*son[1]);
					son[1]->Add(add);
				}
				add=0;
			}
		}
		void Up() {
			sumv=val;
			size=1;
			son[0] && (sumv+=son[0]->sumv,size+=son[0]->size);
			son[1] && (sumv+=son[1]->sumv,size+=son[1]->size);
		}
	};
	static MemPool<Node> Pool;
	typedef shared_ptr<Node> ptr_t;
	ptr_t root;
	Treap(int a[],int n) {
		Build(root,1,n,a);
	}
	typedef std::pair<ptr_t,ptr_t> Pair;
	struct Triple {
		ptr_t first,second,third;
		Triple(ptr_t const &first,ptr_t const &second,ptr_t const &third):first(first),second(second),third(third) {}
	};
	static void Build(ptr_t &pos,int L,int R,int a[]) {
		if(L<=R) {
			int M=(L+R)>>1;
			pos=new Node(a[M]);
			Build(pos->son[0],L,M-1,a);
			Build(pos->son[1],M+1,R,a);
			pos->Up();
		}
	}
	Triple Split(int l,int r) {
		Pair spl=Split(root,l-1),spr=Split(spl.second,r-l+1);
		return Triple(spl.first,spr.first,spr.second);
	}
	ptr_t Merge(Triple const &nodes) {
		return Merge(nodes.first,Merge(nodes.second,nodes.third));
	}
	static Pair Split(ptr_t pos,int K) {
		if(K==0 || pos->size==K) {
			return K==0
				?Pair(0,new Node(*pos))
				:Pair(new Node(*pos),0);
		} else {//pos的son 和p1,p2的son 是不同的！
			pos=new Node(*pos);
			pos->Down();
			int left=(pos->son[0]?pos->son[0]->size:0)+1;
			if(K<left) {
				Pair res=Split(pos->son[0],K);
				pos->son[0]=res.second;
				pos->Up();
				res.second=pos;
				return res;
			} else {
				Pair res=Split(pos->son[1],K-=left);
				pos->son[1]=res.first;
				pos->Up();
				res.first=pos;
				return res;
			}
		}
	}
	static ptr_t Merge(ptr_t p1,ptr_t p2) {
		if(!p1 || !p2) {
			return p1?p1:p2;
		} else {
			if(rand()%(p1->size+p2->size)<p1->size) {
				ptr_t pos=new Node(*p1);
				pos->Down();
				pos->son[1]=Merge(pos->son[1],p2);
				pos->Up();
				return pos;
			} else {
				ptr_t pos=new Node(*p2);
				pos->Down();
				pos->son[0]=Merge(p1,pos->son[0]);
				pos->Up();
				return pos;
			}
		}
	}
};
MemPool<Treap::Node> Treap::Pool(MAXNODE);
int main() {
	srand(0x1f1f1f1f);
	static int a[MAXN];
	int n,Q;is>>n>>Q;
	for(int i=1;i<=n;is>>a[i++]);
	Treap tr(a,n);
	for(int rep=1;rep<=Q;++rep) {
		int op,l,r;is>>op>>l>>r;
		switch(op) {
			case 1: {
				tr.Add(l,r,get());
			} break;
			case 2: {
				tr.Replace(l,(int)get()+1,r);
			} break;
			case 3: {
				os<<tr.Sum(l,r)<<'\n';
			} break;
		}
	}
	return 0;
}

UR练习记

发表于 2017-06-27 | 更新于 2018-06-18

uoj14 DZY Loves Graph

看起来很有趣的样子。。

Solution

如果没有恢复操作，那么插入和删除的总量是 $O(m)$ 的，所以可以暴力删边。只会删除大边，不会删除小边，所以不存在断开需要重新链接的情况。用一个栈实现就行。

MD撤销指的是撤销前一次操作qwq。。'

折样的话，把操作离线，就可以知道下一个操作是不是return。如果是的话特殊处理一下就好了。。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char &ch) {
		while(!isValid(ch=getchar()));
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=3e5+11,MAXQ=5e5+11;
struct OffQ {
	int opt,a,b,k;
}p[MAXQ];
int dsu[MAXN],size[MAXN];
int Root(int x) {
	return dsu[x]?Root(dsu[x]):x;
}
int Merge(int x,int y) {
	if(size[x]<size[y]) {
		std::swap(x,y);
	}
	dsu[y]=x;
	size[x]+=size[y];
	return y;
}
void CutOff(int x) {
	size[dsu[x]]-=size[x];
	dsu[x]=0;
}
int main() {
	int n,Q;is>>n>>Q;
	for(int i=1;i<=Q;++i) {
		OffQ &o=p[i];
		char opt[20];
		is>>opt;
		switch(opt[0]) {
			case 'A': {
				o.opt=1;
				is>>o.a>>o.b;
			} break;
			case 'D': {
				o.opt=2;
				is>>o.k;
			} break;
			case 'R': {
				o.opt=3;
			}
		}
	}
	for(int i=1;i<=n;size[i++]=1);
	static int stack[MAXQ],top,opu[MAXQ],cnt[MAXQ];
	static int64 weight[MAXQ];
	for(int i=1;i<=Q;++i) {
		OffQ &o=p[i];
		switch(o.opt) {
			case 1: {
				stack[++top]=i;
				opu[i]=Root(o.a)==Root(o.b)
					?(cnt[top]=cnt[top-1],weight[top]=weight[top-1],0)
					:(cnt[top]=cnt[top-1]+1,weight[top]=weight[top-1]+i,Merge(Root(o.a),Root(o.b)));
				os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
				if(p[i+1].opt==3) {
					if(opu[stack[top]]) {
						CutOff(opu[stack[top]]);
					}
					top--;
					os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
					++i;
				}
			} break;
			case 2: {
				if(p[i+1].opt!=3) {
					for(int rep=1;rep<=o.k;++rep) {
						if(opu[stack[top]]) {
							CutOff(opu[stack[top]]);
						}
						top--;
					}
					os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
				} else {
					os<<(cnt[top-o.k]==n-1?weight[top-o.k]:0)<<'\n'<<(cnt[top]==n-1?weight[top]:0)<<'\n';
					++i;
				}
			} break;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#include <ext/rope>
#define ext __gnu_cxx
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char &ch) {
		while(!isValid(ch=getchar()));
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=3e5+11,MAXQ=5e5+11,MAXLOGQ=20;
int n;
struct State {
	ext::rope<int> dsu,size;
	int64 weight;int cnt,par[MAXLOGQ];
	State& operator =(State const &other) {
		new(&dsu) ext::rope<int>(other.dsu);
		new(&size) ext::rope<int>(other.size);
		weight=other.weight;
		cnt=other.cnt;
		for(int i=0;i<=19;par[i]=other.par[i],++i);
		return *this;
	}
	int Root(int x) {
		return dsu[x]?Root(dsu[x]):x;
	}
	void AddEdge(int x,int y,int c) {
		x=Root(x),y=Root(y);
		if(x!=y) {
			weight+=c;
			cnt++;
			if(size[x]<size[y]) {
				std::swap(x,y);
			}
			dsu.replace(y,x);
			size.replace(x,size[x]+size[y]);
		}
	}
	void Show() {
		os<<(cnt==n-1?weight:0)<<'\n';
	}
}state[MAXQ];
int Jump(int x,int k) {
	for(int lg=19;~lg;--lg) {
		if(k>>lg&1) {
			x=state[x].par[lg];
		}
	}
	return x;
}
int main() {
	int Q;is>>n>>Q;
	static int temp[MAXN];
	state[0].weight=state[0].cnt=0;
	new(&state[0].dsu) ext::rope<int>(temp,temp+1+n);
	for(int i=1;i<=n;temp[i++]=1);
	new(&state[0].size) ext::rope<int>(temp,temp+1+n);
	int lastAdd=0;
	for(int i=1;i<=Q;++i) {
		char opt[20];
		is>>opt;
		switch(opt[0]) {
			case 'A': {
				state[i]=state[i-1];
				int x,y;is>>x>>y;
				state[i].AddEdge(x,y,i);
				state[i].par[0]=lastAdd;
				for(int lg=1;lg<=19;++lg) {
					state[i].par[lg]=state[state[i].par[lg-1]].par[lg-1];
				}
				lastAdd=i;
			} break;
			case 'D': {
				int k;is>>k;
				state[i]=state[lastAdd=Jump(i-1,k)];
			} break;
			case 'R': {
				state[i]=state[i-2];
			} break;
		}
		state[i].Show();
	}
	return 0;
}

可持久化的做法，MLE自不必说，居然还有WA？但是不想调了。。

uoj21 缩进优化

答案居然不是单峰的qwq

但是对于所有/ts不变的块内的最小值是单峰的，答案肯定在那里面。

~~于是我会了一种 $O(n\sqrt a)$ 的做法。。MDZZ~~

Solution

整除不禁让人想起了经典的数论分块。。

要分块就要想办法把这个mod消掉

只要对 $a_i$ 的个数搞一个前缀和就可以得到 $70$ 分啦！！

然后呢？

为什么要枚举 $a_i$ 呢？枚举 $[\frac {a_i}x]$ 啊！然后就AC了。

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
template <class T> inline
bool Relax(T &a,T const &b) {
	return a<b?a=b,1:0;
}
const int MAXN=1e6+11;
int main() {
	static int a[MAXN],cnt[MAXN];
	int n;is>>n;
	int64 sum=0;
	int maxA=0;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		++cnt[a[i]];
		sum+=a[i];
		Relax(maxA,a[i]);
	}
	for(int i=1;i<=maxA;cnt[i]+=cnt[i-1],++i);
	int64 maxs=0;
	for(int ts=2;ts<=maxA;++ts) {
		int64 temp=0;
		for(int dv=1;dv*ts<=maxA;++dv) {
			temp+=(int64)(cnt[std::min(maxA,dv*ts+ts-1)]-cnt[dv*ts-1])*dv;
		}
		Relax(maxs,temp*=(ts-1));
	}
	int64 Ans=sum-maxs;
	os<<Ans<<'\n';
	return 0;
}

uoj22 外星人

在模的过程中，值一定是越来越小的，绝对值越来越大。
然后我想想？
大的永远不会影响，可以用组合数计算

Solution

先想如何求最大值？？

一个点后面所有比它大的值都不会影响答案。

一个有效的操作序列是一个下降序列。

相当于排完序求一个子序列，膜完剩下最大。然后随便DP，就有36分。

依然延续求第一问的思路，现在考虑如何求出方案数。

其实都是一样的，也就是分两种情况讨论一下：废掉这个，还是用掉这个。

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1e3+11,MAXA=5e3+11,P=(7*17<<23)+1;
int main() {
	int n=is,x=is;
	static int a[MAXN];
	for(int i=1;i<=n;is>>a[i++]);
	std::sort(a+1,a+1+n,std::greater<int>());
	static int64 f[MAXN][MAXA];
	f[0][x]=1;
	for(int i=1;i<=n;++i) {
		for(int v=0;v<=x;++v) {
			(f[i][v%a[i]]+=f[i-1][v])%=P;
			(f[i][v]+=f[i-1][v]*(n-i)%P)%=P;
		}
	}
	int mxv=x;
	for(;!f[n][mxv];mxv--);
	os<<mxv<<' '<<f[n][mxv]<<'\n';
	return 0;
}

弄明白之后才感觉自己真SB。

跳蚤国王下江南

毒瘤啊。。

uoj31 猪猪侠再战括号序列

直接暴力构造应该就有50分吧。。

并不是。。暴力构造可能会有 $2n$ 步。。zz.

最多只需要转 $n$ 下。

用Splay维护就A了？2333

~~可以看成一次操作需要成全一对我忽略了什么？为什么毫无思路？？？？？？~~

def fuck():
	print "Fuck You"
while 1:
	fuck()

Solution

正解的思路，和暴力构造是一个意思。

只是找左括号的时候要找右边第一个。

你猜怎么着？中间都是右括号，根本不会变，翻转变成 $O(1)$ 的了！！！

而左括号的位置是有单调性的！！！

Tips

错误的估计了暴力的正确性qwq 否则应该还是能想出来的

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=1e5+11;
template <class T> inline
bool Relax(T &a,T const &b) {
	return a<b?a=b,1:0;
}
int main() {
	static char s[MAXN<<1];
	is>>(s+1);
	int n=strlen(s+1)/2;
	std::vector<std::pair<int,int> > Ans;
	for(int i=1,pt=1,sum=0;i<=n*2;++i) {
		if((sum+=s[i]=='('?1:-1)<0) {
			for(Relax(pt,i+1);s[pt]!='(';++pt);
			Ans.push_back(std::pair<int,int>(i,pt));
			std::swap(s[i],s[pt]);
			sum+=2;
		}
	}
	os<<Ans.size()<<'\n';
	for(size_t i=0;i<Ans.size();++i) {
		os<<Ans[i].first<<' '<<Ans[i].second<<'\n';
	}
	return 0;
}

uoj32 跳蚤公路

先SCC一下。求出每个SCC的最大最小值一个点的答案就是从1能到、且能到v的scc中去一个交集还是二分吗折样的话这一部分总复杂度是 $O(nm\log x)$ 的然后就能搞了？？没法直接二分啊XD 应该可以二分。。但是会很麻烦啊qwq ~~## Tips 发现满足可二分性质的东西，看看是否可以列成一个可以解的式子，由判定转为求值为什么不会分成两段？？？？~~

Solution

真是一道好题。。。。。

写一个详细的Solution吧。。。

开始口胡

首先题意中的挣钱道路就是负权回路。判断一张图有没有负权回路是“经典问题”，可以用Bellman-Ford来做。再想想，不存在负权回路的应该是数轴上一段连续的区间，所以满足可二分性。至于怎么二分？先代入一下最大值，再代入一下最小值，如果是负的就二分找正的，否则二分找负的。

直接做复杂度是 $O(n^2m\log 10^{31})$ 的，显然不科学。

考虑一点性质：一个SCC里面，所有点不存在负权回路的上下界都应该相同。所以可以对每个SCC单独搞，计算答案的时候，找出所有能到达的SCC把上下界取交集即可。。最后应该能 $O(nm\log {10^{31}})$ 了吧。。。

这个应该能做啊。。但我想出来之后去看题解发现这个似乎不科学？？？

口胡结束

于是学习了一番std

判断是否有负权回路，经典做法是Bellman-Ford。在第 $n$ 次松弛如果依然有被松弛的说明它就在一个含有负权回路的路径上。

而现在还存在这一个系数 $k\in [-n,n]$ ，那就设 $f[s][k][p]$ 表示走了 $s$ 步，系数为 $k$ ，到了点 $p$ 的最短路，转移显然。

最后要满足的条件，是 $\forall p\ \min\{kx+f[n][k][p]\}\ge \min\{hx+f[n][h][p]\}$

这个条件怎么解呢？

首先显然不同的 $p$ 是独立的，那就固定 $p$ ，然后，再固定一维 $k$ 。 $p$ 可行区间就是对每个 $k$ 解出来 $kx+f[n][k][p]\ge \min\{hx+f[n][h][p]\}$ 最后把范围取个交集。

最后考虑这个怎么解 $kx+f[n][k][p]\ge hx+f[n][h][p]$ 。其实就是对每个 $h$ 解出来把范围取个并集。

先并集后交集这个很难搞，那就转化成对补集先交集再并集。补集的并集也没什么好办法，用vector存下来就行了。

最后计算答案，就枚举一下所有从1能到，而且能到 $p$ 的点 $u$ ，把 $u$ 的那些补集都插入到一个vector。最后把这些补集取个并集，再补集一下就是答案。这个部分就简单多了：因为众所周知最后的答案一定是一个连续的区间，那么补集之多只会出现一段的空缺。找出这一段，就是最后的答案了。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1e2+11,MAXM=1e4+11;
const int64 INF=0x1f1f1f1f1f1f1f1f;
template <class T> inline bool Tension(T &a,T const &b) { return a>b?a=b,1:0; }
template <class T> inline bool Relax(T &a,T const &b) { return a<b?a=b,1:0; }
int64 Floor(int64 const &a,int64 const &b) { return a/b-((a>0)!=(b>0)); }
int64 Ceil(int64 const &a,int64 const &b) { return a/b+((a>0)==(b>0)); }
int main() {
	static bool con[MAXN][MAXN];
	static struct Edge { int x,y,w,k; }edges[MAXM];
	int n=is,m=is;
	for(int i=1;i<=m;++i) {
		Edge &e=edges[i];
		is>>e.x>>e.y>>e.w>>e.k;
		con[e.x][e.y]=1;
	}
	for(int i=1;i<=n;con[i][i]=1,++i);
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				con[i][j]|=con[i][k] & con[k][j];
			}
		}
	}

	static int64 f[MAXN][MAXN<<1][MAXN];//走几步 系数是多少 停在哪里 最短路
	memset(f[0],31,sizeof(f[0]));
#define MG(i) ((i)+n)
	f[0][MG(0)][1]=0;
	for(int st=0;st<=n-1;++st) {
		memcpy(f[st+1],f[st],sizeof(f[st]));
		for(int k=-st;k<=st;++k) {
			for(int i=1;i<=m;++i) {
				Edge &e=edges[i];
				f[st][MG(k)][e.x]!=INF && Tension(f[st+1][MG(k)+e.k][e.y],f[st][MG(k)][e.x]+e.w);
			}
		}
	}
	static std::vector<std::pair<int64,int64> > isci[MAXN];
	for(int pos=1;pos<=n;++pos) {
		int64 kv,hv;
		for(int k=-n;k<=n;++k) if((kv=f[n][MG(k)][pos])!=INF) {
			int64 l=-INF,r=INF;
			for(int h=-n;h<=n;++h) if((hv=f[n-1][MG(h)][pos])!=INF) {
				if(k>h) {
					Tension(r,(hv-kv)%(k-h)==0?(hv-kv)/(k-h)-1:Floor(hv-kv,k-h));
				} else if(k<h) {
					Relax(l,(hv-kv)%(k-h)==0?(hv-kv)/(k-h)+1:Ceil(hv-kv,k-h));
				} else if(kv>=hv) {
					l=INF;
					r=-INF;
					break;
				}
			}
			if(l<=r) {
				isci[pos].push_back(std::pair<int64,int64>(l,r));
			}
		}
	}
	for(int pos=1;pos<=n;++pos) {
		std::vector<std::pair<int64,int64> > isc;
		for(int u=1;u<=n;++u) if(con[1][u] && con[u][pos]) {
			std::copy(isci[u].begin(),isci[u].end(),std::back_inserter(isc));
		}
		std::sort(isc.begin(),isc.end());
		int64 l=INF,r=-INF;
		if(isc.empty()) {
			l=-INF,r=INF;
		} else if(isc.front().first!=-INF) {
			l=-INF;r=isc.front().first-1;
		} else {
			int64 cm=-INF;bool found=0;
			for(size_t i=0;i<isc.size();++i) {
				if(isc[i].first>cm+1) {
					l=cm+1;
					r=isc[i].first-1;
					found=1;
					break;
				}
				Relax(cm,isc[i].second);
			}
			if(!found && cm!=INF) {
				l=cm+1;
				r=INF;
			}
		}
		if(l>r) {
			os<<0<<'\n';
		} else {
			os<<(l==-INF || r==INF?-1:r-l+1)<<'\n';
		}
	}
	return 0;
}

uoj33 树上gcd

看着就好神啊。。。。。

直接点分治？？分个头。。

怎么做怎么做？？？？？？？？？？

Solution

官方题解给了两种做法, $O(n\sqrt n)$ 和 $O(n\sqrt n\log n)$

$O(n\sqrt n\log n)$

这种做法复杂度不优秀但是比较好写，也比较神奇。

要求 $\gcd(d_u,d_v)=x$ 的数目，可以转化成 $x|d_u,x|d_v$ 的数目，最后反演一下就好了！！！（蒟蒻觉得很腻害！）

首先在一条链上的比较好做。。这一部分不用反演。一个点对答案的贡献是区间+1，这样用差分实现，最后一遍前缀和就行了。

剩下的部分，也就是不是直上直下的点对，咋做？

对于 $d\le \sqrt n$ ，大力dp

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=2e5+11;
const int SB=10;
#define int64 long long
std::vector<int> son[MAXN],h[MAXN];
int64 Ans[MAXN];
int dep[MAXN],fa[MAXN],f[MAXN][SB+1],g[MAXN][SB+1];
void DFS(int pos) {
	static int stack[MAXN],top;
	stack[++top]=pos;
	for(int u : son[pos]) {
		DFS(u);
	}
	if(pos!=1) {
		//f 正好的 g 差1的
		for(int d=1;d<=SB;++d) {//必须要算满SB 因为还有下面的！！见2、3行
			g[stack[std::max(top-d+1,0)]][d]+=f[pos][d]+1;
			Ans[d]+=(int64)f[fa[pos]][d]*g[pos][d];
			f[fa[pos]][d]+=g[pos][d];
		}
		h[pos].push_back(1);
		if(h[fa[pos]].size()<h[pos].size()) {
			std::swap(h[fa[pos]],h[pos]);
		}
		std::vector<int> &a=h[fa[pos]],&b=h[pos];
		int sizeA=a.size(),sizeB=b.size();
		if(sizeA>SB && sizeB>SB) {
			for(int d=SB+1;d<=sizeB;++d) {
				int sumA=0;
				for(int len=d;len<=sizeA;sumA+=a[sizeA-len],len+=d);
				int sumB=0;
				for(int len=d;len<=sizeB;sumB+=b[sizeB-len],len+=d);
				Ans[d]+=(int64)sumA*sumB;
			}
		}
		for(int d=1;d<=sizeB;a[sizeA-d]+=b[sizeB-d],++d);
		b.clear();
	}
	top--;
}
int main() {
	int n=is;
	static int64 cnt[MAXN];
	for(int i=2;i<=n;++i) {
		dep[i]=dep[fa[i]=is]+1;
		++cnt[1];--cnt[dep[i]+1];
		son[fa[i]].push_back(i);
	}
	for(int i=1;i<=n-1;cnt[i]+=cnt[i-1],++i);
	DFS(1);
	for(int i=n-1;i>=1;--i) {
		for(int j=i*2;j<=n-1;j+=i) {
			Ans[i]-=Ans[j];
		}
	}
	for(int i=1;i<=n-1;++i) {
		Ans[i]+=cnt[i];
		os<<Ans[i]<<'\n';
	}
	return 0;
}

uoj48 核聚变反应强度

大水题啊。。不写了。。

uoj49 铀仓库

可以三分套二分吧。。 $O(n\log^2n)$

不需要三分时间，只需要二分距离！

MD各种爆int爆ll被卡晕了

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=5e5+11;
int n,a[MAXN],x[MAXN];
long long tlim,pref_sum[MAXN];
bool check(long long cnt) {
	if(cnt==a[0]) {
		return 1;
	} else {
		static int chs[MAXN];
		std::fill(chs+1,chs+1+n,0);
		int l=1,r=1;chs[1]=a[1];long double tuse=0;
		for(long long sum=a[1];sum<cnt;) {
			++r;
			chs[r]=sum+a[r]<=cnt?a[r]:cnt-sum;
			sum+=chs[r];
			tuse+=(long double)(chs[r])*(x[r]-x[1]);
		}
		if(2*tuse<=tlim) return 1;
		for(int i=2;i<=n;++i) {
			tuse+=(long double)(x[i]-x[i-1])*((pref_sum[i-1]-pref_sum[l]+chs[l])-(pref_sum[r-1]-pref_sum[i-1]+chs[r]));
			while(x[i]-x[l]>x[r]-x[i]) {
				int d=std::min(a[r]-chs[r],chs[l]);
				tuse+=(long double)(d)*(x[l]+x[r]-2*x[i]);
				(chs[l]-=d)==0 && ++l;
				(chs[r]+=d)==a[r] && ++r;
			}
			if(2*tuse<=tlim) return 1;
		}
		return 0;
	}
}
int main() {
	is>>n>>tlim;
	for(int i=1;i<=n;is>>x[i++]);
	x[n+1]=2e9+1e8;
	for(int i=1;i<=n;pref_sum[i]=pref_sum[i-1]+(a[i]=is),++i);
	long long L=a[0]=*std::max_element(a+1,a+1+n),R=pref_sum[n];
	while(L!=R) {
		long long M=(L+R+1)>>1;
		check(M)?L=M:R=M-1;
	}
	os<<L<<'\n';
	return 0;
}
//WA??

uoj50 链式反应

现在我知道这道题是fft。。然后呢？？

每个中子呈树状展开，最后有多少棵(带编号)不同的树

转移明显是没有后效性的。。吗并不是。。因为死光的操作很烦人。。 $f[i]$ 一个点爆炸后面有 $i$ 个完好的方案数枚举中子打到的位置 $O(n^2)$ 可以把那 $i$ 个分成三段再枚举射死多少 $O(n)$ 再枚举在三段里面分别射死多少 $O(n^2)$ 就可以DP了吧复杂度 $O(n^6)$ 不行。。 $f[i][j]$

MDZZ

要么这个囧-2333原子变为了囧-2334 并不再参与后续反应

又tm没看题目！！！！！

那就好做点了吗？

$f[i]$ 表示 $i$ 的答案。

转移的时候不枚举编号，枚举梓树大小！！！还是用树的思维来思考，从大小来考虑好一些。因为大小是比编号更加重要的因素，而知道编号没法推出大小，但是知道大小可以随便重编号！！！树树树！！！

40pts

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	bool isValid(char ch) { return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF; }
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=200+11,P=(7*17<<23)+1,inv2=499122177;
int main() {
	int n=is;
	static char s[MAXN];
	is>>s;
	static long long C[MAXN][MAXN];
	for(int i=0;i<=n;++i) 
		for(int j=0;j<=i;++j) 
			C[i][j]=j==0 || j==i?1:(C[i-1][j-1]+C[i-1][j])%P;
	static long long f[MAXN];
	f[1]=1;
	f[2]=0;
	for(int i=3;i<=n;++i)
		for(int j=1;j<=i-1;++j) 
			for(int k=1;k<=i-1-j;++k)
				if(s[i-1-j-k]=='1') 
					(f[i]+=C[i-1][i-1-j-k]*C[j+k][j]%P*f[j]%P*f[k]%P*inv2%P)%=P;
	for(int i=1;i<=n;++i) 
		os<<f[i]<<(i==n?'\n':' ');

	return 0;
}
//诡异的类型转换

uoj51 元旦三侠的游戏

Solution

如果 $n$ 小一些的话就能做了吗。

Tips

调用sqrt()不总能达到想要的效果。。要求高的整数开方可以自行二分。。。。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
	template <class T>
	Ostream &operator <<(T *s) {
		while(*s) *this<<*s++;
		return *this;
	}
}os;
const int MAXSQRTN=4e4,MAXLOGN=31;
int main() {
	int n=is,Q=is,m=1;
	while((m+1)*(m+1)<=n) ++m;
	static int end[MAXSQRTN],win[MAXSQRTN][MAXLOGN];
	for(int a=2;a<=m;++a) {
		end[a]=0;
		for(long long x=1;x<=n;x*=a,++end[a]);
	}
	end[m+1]=1;
	for(int a=m;a>=2;--a)
		for(int b=end[a]-1;b>=1;--b)
			win[a][b]=(b+1<end[a] && !win[a][b+1]) || (b<end[a+1] && !win[a+1][b]);
	while(Q--) {
		int a=is,b=is;
		os<<((a<=m?win[a][b]:(n-a)&1)?"Yes":"No")<<'\n';
	}
	return 0;
}

JZPKIL

发表于 2017-06-26 | 更新于 2018-06-18

Link

Solution

\begin{aligned} &\sum_{i=1}^n(i,n)^x[i,n]^y\\ =&n^y\sum_{i=1}^n(i,n)^{x-y}i^y\\ \end{aligned}

依旧设

f(x)=\sum_{d|x}g(d)

g(x)=\sum_{d|x}\mu(\frac xd)f(d)

那么

设

S(n,x)=\sum_{i=1}^ni^x

则

MDZZ。。。。被套路带偏。。重来。

\begin{aligned} &\sum_{i=1}^n(i,n)^x[i,n]^y\\ =&n^y\sum_{i=1}^n(i,n)^{x-y}i^y\\ \end{aligned}

怎样跑得更快，是可以引入辅助函数来把gcd去掉的，因为函数值可以暴力算。然而这个显然不行。。。

这样的话，前后部分独立，那就看后面的那个部分。设原式子为

\begin{aligned} S(n)&=\sum_{i\perp n,i\le n}i^y\\ &=\sum_{i=1}^{n}i^y\sum_{d|i,d|n}\mu(d)\\ &=\sum_{d|n}\mu(d)\sum_{d|i}i^y\\ &=\sum_{d|n}\mu(d)d^y\sum_{i'=1}^{\frac nd}i^y \end{aligned}

设

S_k(n)=\sum_{i=1}^n i^k

\begin{aligned} &\sum_{d|n}\mu(d)d^y\sum_{i'=1}^{\frac nd}i^y\\ =&\sum_{d|n}\mu(d)d^yS_y(\frac nd) \end{aligned}

回代，

Code

uoj62 怎样跑得更快

发表于 2017-06-26 | 更新于 2018-06-18

Link

给定 $n,c,d,P=998244353,b_1,...,b_n\in[1,P)$ ，

解出 $x_1,...,x_n$ 满足

Solution

搞出一个辅助函数 $g(x)$ 满足

f(x)=\sum_{d|x}g(d)

代入有

设

h(d)=\sum\limits_{d|i}x'_i

则

求出来 $g(i)h(i)$ 就有了 $h(i)$

有了 $h(i)$ 我感觉已经忘了一开始要求什么了。。

哦对了

h(d)=\sum_{d|i}x'_i

Tips

一定要弄清反演的方向！！！

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int P=(7*17<<23)+1,MAXN=1e5+11;
int64 Pow(int64 base,int index,int P) {
	static int64 res;
	(index%=P-1)<0 && (index+=P-1);
	for(res=P!=1,base%=P;index;index&1 && ((res*=base)%=P),index>>=1,(base*=base)%=P);
	return res;
}
int Inverse(int x,int P) {
	return Pow(x,P-2,P);
}
int main() {
	int n,c,d,Q;
	is>>n>>c>>d>>Q;
	static int64 g[MAXN],f[MAXN],ig[MAXN],inv[MAXN];
	for(int i=1;i<=n;++i) {
		inv[i]=Inverse(i,P);
		(g[i]+=(f[i]=Pow(i,c-d,P)))%=P;
		ig[i]=Inverse(g[i],P);
		for(int j=i*2;j<=n;j+=i) {
			(g[j]-=g[i])%=P;
		}
	}
	for(int rep=1;rep<=Q;++rep) {
		static int64 b[MAXN],h[MAXN],gh[MAXN],x[MAXN];
		for(int i=1;i<=n;++i) {
			is>>b[i];
			(b[i]*=Pow(inv[i],d,P))%=P;
		}
		for(int i=1;i<=n;gh[i]=b[i],++i);
		bool tak=1;
		for(int i=1;i<=n;++i) {
			for(int j=i*2;j<=n;j+=i) {
				(gh[j]-=gh[i])%=P;
			}
			if(gh[i] && !g[i]) {
				tak=0;
				break;
			} else {
				h[i]=gh[i]*ig[i]%P;
			}
		}
		if(tak==0) {
			os<<-1<<'\n';
		} else {
			for(int i=1;i<=n;x[i]=h[i],++i);
			for(int i=n;i>=1;--i) {
				for(int j=i*2;j<=n;j+=i) {
					(x[i]-=x[j])%=P;
				}
			}
			for(int i=1;i<=n;++i) {
				(x[i]*=Pow(inv[i],d,P))%=P;
				x[i]<0 && (x[i]+=P);
				os<<x[i]<<(i==n?'\n':' ');
			}
		}
	}
	return 0;
}

uoj195 大森林

发表于 2017-06-26 | 更新于 2018-06-18

Link

Solution

很不错的数据结构题目！

首先要注意到，只要得到一个树木的最终形态，就可以回答与这棵树有关的所有询问。因为只存在在下面加点的操作，上方的点怎么也不会被影响到。

那就考虑如何得到每个树木的最终形态。

先把

Code

#include <bits/stdc++.h>
const int IN=1e7;
char inBuf[IN],*iptr=inBuf;
#define getchar() (*iptr==0 && (inBuf[fread(iptr=inBuf,1,IN,stdin)]=0,*iptr==0)?EOF:*iptr++)
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
const int OUT=1e7;
char outBuf[OUT],*optr=outBuf;
const char EOB=outBuf[OUT-1]=-1;
#define putchar(x) ((*optr==EOB && (fwrite(outBuf,1,OUT,stdout),optr=outBuf),*optr++)=(x))
struct Ostream {
	~Ostream() {
		fwrite(outBuf,1,optr-outBuf,stdout);
	}
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=1e5+11,MAXQ=2e5+11;
template <class T> inline
bool chkmx(T &a,T const &b) {
	return a<b?a=b,1:0;
}
template <class T> inline
bool chkmn(T &a,T const &b) {
	return a>b?a=b,1:0;
}
struct LCT {
	int Dist(int x,int y) {
		//2情况
		Node *px=node[x],*py=node[y];
		BeRoot(px);
		Touch(py);
		int res=py->sumv-LCA(px,py)->val;
		return res;
	}
	void LinkTo(int x,int fa) {
		BeRoot(node[x]);
		node[x]->fa=node[fa];
	}
	void CutOff(int x) {
		BeRoot(node[1]);
		Node *pos=node[x];
		Touch(pos);
		pos->Down();
		pos->son[0]=pos->son[0]->fa=null;
		pos->Up();
	}
	void Insert(int val) {
		node.push_back(new Node(val));
	}
	struct Node {
		Node *son[2],*fa;
		int sumv,val;
		bool rev;
		Node(int val):sumv(val),val(val),rev(0) {
			son[0]=son[1]=fa=null;
		}
		Node(bool):sumv(0),val(0),rev(0) {
			son[0]=son[1]=fa=0;
		}
		bool isRoot() {
			return fa->son[0]!=this && fa->son[1]!=this;
		}
		bool Kind() {
			return fa->son[1]==this;
		}
		void Rev() {
			std::swap(son[0],son[1]);
			rev^=1;
		}
		void Down() {
			if(rev) {
				son[0]->Rev();
				son[1]->Rev();
				rev=0;
			}
		}
		void Up() {
			sumv=son[0]->sumv+son[1]->sumv+val;
		}
	};
	static Node *null;
	std::vector<Node*> node;
	LCT() {
		node.push_back(null);
	}
	Node *LCA(Node *p1,Node *p2) {
		BeRoot(node[1]);
		Access(p1);
		return Access(p2);
	}
	static void Trans(Node *pos) {
		Node *fa=pos->fa,*grand=fa->fa;
		fa->Down();pos->Down();
		int d=pos->Kind();
		if(!fa->isRoot()) {
			grand->son[fa->Kind()]=pos;
		}
		pos->fa=grand;
		pos->son[!d]->fa=fa;fa->son[d]=pos->son[!d];
		pos->son[!d]=fa;fa->fa=pos;
		fa->Up();
	}
	static void Splay(Node *pos) {
		for(Node *fa;!pos->isRoot();Trans(pos)) {
			if(!(fa=pos->fa)->isRoot()) {
				Trans(fa->Kind()==pos->Kind()?fa:pos);
			}
		}
		pos->Up();
	}
	static void BeRoot(Node *pos) {
		Touch(pos);
		pos->Rev();
	}
	static void Touch(Node *pos) {
		Access(pos);
		Splay(pos);
	}
	static Node *Access(Node *pos) {
		static Node *pred;
		for(pred=null;pos!=null;pred=pos,pos=pos->fa) {
			Splay(pos);
			pos->Down();
			pos->son[1]=pred;
			pos->Up();
		}
		return pred;
	}
};
LCT::Node *LCT::null=new LCT::Node(true);
struct DarkOpt {
	int opt,pos,a,b,*Ans;
	DarkOpt(int opt,int pos,int a,int b,int *Ans=0):opt(opt),pos(pos),a(a),b(b),Ans(Ans) {}
	friend bool operator <(DarkOpt const &lhs,DarkOpt const &rhs) {
		return lhs.pos<rhs.pos || (lhs.pos==rhs.pos && lhs.opt<rhs.opt);
	}
};
int main() {
	/*
	   我想想
	   为每个1操作加入一个虚点作为生长节点
	   遍历每个子树
	 */
	int n,Q;is>>n>>Q;
	std::vector<DarkOpt> opt;opt.reserve(Q<<1);
	std::vector<int> Ans;Ans.reserve(Q);
	LCT lct;
	static int lbd[MAXQ],rbd[MAXQ],idr[MAXQ],reac,lastVi,noc;
	lbd[reac=1]=1;rbd[1]=n;
	idr[1]=1;
	lct.Insert(1);
	lbd[noc=2]=1;rbd[2]=n;
	lastVi=noc;
	lct.Insert(0);
	lct.LinkTo(2,1);
	for(int rep=1;rep<=Q;++rep) {
		int op;is>>op;
		switch(op) {
			case 0: {
				//newNode
				idr[++reac]=++noc;
				is>>lbd[reac]>>rbd[reac];
				lct.Insert(1);
				lct.LinkTo(idr[reac],lastVi);
			} break;
			case 1: {
				//changeGrow
				int l,r,x;is>>l>>r>>x;
				chkmx(l,lbd[x]);
				chkmn(r,rbd[x]);
				if(l<=r) {
					int newVi=++noc;
					lct.Insert(0);
					lct.LinkTo(newVi,lastVi);
					//这个修改没有生效的时候 是要连接到上一个虚点上的
					opt.push_back(DarkOpt(1,l,newVi,idr[x]));
					opt.push_back(DarkOpt(1,r+1,newVi,lastVi));
					lastVi=newVi;
				}
			} break;
			case 2: {
				int x,u,v;is>>x>>u>>v;
				Ans.push_back(-1);
				opt.push_back(DarkOpt(2,x,idr[u],idr[v],&Ans.back()));
			} break;
		}
	}
	std::sort(opt.begin(),opt.end());
	for(size_t i=0;i<opt.size();++i) {
		DarkOpt &o=opt[i];
		switch(o.opt) {
			case 1: {
				lct.CutOff(o.a);
				lct.LinkTo(o.a,o.b);
			} break;
			case 2: {
				*o.Ans=lct.Dist(o.a,o.b);
			} break;
		}
	}	
	for(size_t i=0;i<Ans.size();++i) {
		os<<Ans[i]<<'\n';
	}
	return 0;
}

triple

发表于 2017-06-14 | 更新于 2018-06-18

令 $j=j'd,k=k'd$

\begin{aligned} &\sum_{i=1}^a\sum_d\mu(d)\sum_{j=1,i\perp j,d|j}^b\sum_{k=1,d|k}^c1\\ =&\sum_{i=1}^a\sum_d\mu(d)\sum_{j'=1,i\perp j'd}^{[\frac bd]}\sum_{k'=1,i\perp k'd}^{[\frac cd]}1\\ =&\sum_{i=1}^a\sum_{d\perp i}\mu(d)\sum_{j'=1,i\perp j'}^{[\frac bd]}\sum_{k'=1,i\perp k'}^{[\frac cd]}1\\ \end{aligned}

令 $f(g,x)=\sum\limits_{i=1}^x[i\perp g]$ ，也就是 $\le x$ 与 $g$ 互质的数的个数

则

\begin{aligned} &\sum_{i=1}^a\sum_{d\perp i}\mu(d)\sum_{j'=1,i\perp j'}^{[\frac bd]}\sum_{k'=1,i\perp k'}^{[\frac cd]}1\\ =&\sum_{i=1}^a\sum_{d\perp i}\mu(d)f(i,[\frac bd])f(i,[\frac cd]) \end{aligned}

然后对质因子容斥？

str

发表于 2017-06-14 | 更新于 2018-06-18

Link

Solution

学了SAM总算能做这道题目了qwq。。

按照敦敦敦的论文，要保证从每个串中取出的那个子串在那个串中都是极大的。

所谓极大

设 $n$ 个字符串 $s_i$ ，从第 $i$ 个字符串选出的子串是 $x_i$ ，拼成了 $X$

则

用后缀自动机的话，这个思路就比较明显了。

假如后缀自动机的点 $p$ ，

说明中的串，要是接上 $c$ ，都是满足要求的极大子串。

由此可以计数。

Code

被卡常到怀疑人生。。我都在想是不是Menci的服务器装了假的至强E5。。

#include <cstdio>
#include <string>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ';
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#include <cstdlib>
#include <cstring>
#define int64 long long
enum TestLimits {
	MAXN=(int)1e6+11,
};
const int P=1e9+7;
struct SuffixAutomaton {
	struct Node {
		Node *par,*son[26];
		int rlast,rmax;
		Node(int rlast,int rmax):par(0),rlast(rlast),rmax(rmax) { memset(son,0,sizeof(son)); }
		void *operator new(size_t flag) {
			static Node *Me=(Node*)malloc((MAXN<<1)*sizeof(Node)),*Pool=Me,*temp;
			return flag?Me++:(temp=Me,Me=Pool,temp);
		}
	}*root,*last,*begin,*end;
	SuffixAutomaton(const char *s) {
		root=last=new Node(0,0);
		for(;*s;Extend(*s++));
		begin=root;
		end=(Node*)Node::operator new(0);
	}
	void Extend(char ch) {
		int x=ch-'a';
		Node *newp=new Node(last->rlast+1,last->rmax+1),*vp=last;
		for(;vp && !vp->son[x];vp->son[x]=newp,vp=vp->par);
		if(vp==0) {
			newp->par=root;
		} else {
			Node *vpx=vp->son[x];
			if(vp->rmax+1==vpx->rmax) {
				newp->par=vpx;
			} else {
				Node *o=new Node(*vpx);
				o->rmax=vp->rmax+1;
				//o->right.XXX
				vpx->par=newp->par=o;
				for(;vp && vp->son[x]==vpx;vp->son[x]=o,vp=vp->par);
			}
		}
		last=newp;
	}
};
int64 f[26];//f[x] 以x开头的合法的个数
void Deal(const char *s) {
	static int cnt[MAXN][26];
	static int64 g[26];
	SuffixAutomaton sam(s);
	--s;//下标从1开始了！！
	int n=strlen(s+1);
	for(int i=1;i<=n;++i) {
	//	memcpy(cnt[i],cnt[i-1],sizeof(cnt[0]));
		std::copy(cnt[i-1],cnt[i-1]+26,cnt[i]);
		cnt[i][s[i]-'a']++;
	}
	std::fill(g,g+26,0ll);
	for(SuffixAutomaton::Node *pos=sam.begin+1;pos!=sam.end;++pos) {
		int64 tol=1;
		for(int x=0;x<26;++x) {
			if(!pos->son[x]) {
				tol+=f[x];
			}
		}
		int *sum=cnt[pos->rlast-pos->par->rmax],*anti=cnt[pos->rlast-pos->rmax];
		for(int x=0;x<26;++x) {
			(g[x]+=tol*(sum[x]-anti[x]))%=P;
		}
	}
	for(int x=0;x<26;++x) {
		if(!sam.root->son[x]) {
			(g[x]+=f[x])%=P;
		}
	}
	std::copy(g,g+26,f);
}
int main() {
	static char *str[MAXN],_strPool[MAXN<<1],*strPool=_strPool;
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		str[i]=strPool;
		is>>str[i];
		for(;*strPool;++strPool);
		++strPool;
	}
	for(int i=n;i>=1;--i) {
		Deal(str[i]);
	}
	int64 Ans=1;
	for(int x=0;x<26;++x) {
		Ans+=f[x];
	}
	Ans%=P;
	os<<Ans<<'\n';
	return 0;
}

SuffixAutomaton——世界你赢了

发表于 2017-06-13 | 更新于 2018-06-17

初学

那是在2016年的暑假，我写了几天动态点分治，然后想起来省选R1 day2结束之后，yts问faebdc第一题卡不卡后缀自动机。faebdc说他并不会后缀自动机。然后这道题是一道后缀自动机原题的弱化 $^n$ 版。

年少无知的我开始搜集SAM的资料，开始啃仅有的几份教程。

然而实在是脑子不够灵通，没有看明白。

又学

转眼之间，到了2016年的11月份，我写了几天FFT，然后想起来省选R1 day2结束之后，yts问faebdc第一题卡不卡后缀自动机。faebdc说他并不会后缀自动机。然后这道题是一道后缀自动机原题的弱化 $^n$ 版。

年少无知的我开始搜集SAM的资料，开始啃仅有的几份教程。

然而实在是脑子不够灵通，没有看明白。

然后龙队说他也不会SAM。

我也就有了不再硬啃下去的理由。

然后

转眼到了2017年3月。我发现有很多动态维护字符串的题目，是不好用后缀数组做的，然后想起来省选R1 day2结束之后，Relly说他第一题谢了后缀平衡树，比正解还快，但是因为数组开小，只有暴力分。

年少无知的我开始搜集SBT的资料，开始啃唯一的一篇论文。

SBT易于理解，简洁明了，哲理深刻，意蕴悠长。我用SBT写了几道动态维护字符串的题，比如那道wxh loves string。

然后我自以为万事大吉：静态用SA，动态用SBT。然而现实给了我无情的打击。

再学

转眼之间，几月时间，多少离合悲欢。曾经志在省队少年，化作D类的狗。在省队集训上，PhilipsWeng出了一道和敦敦敦论文题类似的题目，用到的性质，和自动机简直是一拍即合。我发现，即使我能做，但是有些题用SAM的思维来做是会大大降低难度的。

于是我又厚着脸皮开始学SAM。终于，像打通了任督二脉一般，一副自动机的图景在我的面前徐徐展开。

SAM

SuffixAutomaton是一个可以识别字符串的子串的这么一个东西。

要造出可以识别子串的这么一个东西，最简单的就是建一个trie把所有后缀插入。然而这样时间爆炸空间爆炸。

众所周知，字符串总是有很多神奇的性质。充分发掘这些性质，最后可以搞出来时空 $O(n)$ 的神奇效果。

apple

发表于 2017-06-11 | 更新于 2018-06-18

Link

考试的时候连看都没看的题目。。Orz ShallWe A掉此题。。

研究题解，还把题目都看错了，怎么都搞不懂。纸张。

Solution

要求选出一些点让它们变得无用，使得剩下的点的权值和 $\le limit$ 。

可以枚举让哪些点变得无用从而使得权值和符合要求。 $n\le 40$ ，而不同的点的枚举互相独立，可以用meet in the middle。剩下的只需要计算“让一些点变得无用”的方案数目。

让一些点变得无用，也就是钦定这些点必须连-1的点。 $f[i]$ 表示钦定只有 $i$ 个点无用的方案数，不好算，考虑容斥。 $g[i]$ 表示钦定至少 $i$ 个点无用的方案数。那么 $f[i]=\sum\limits_{j=i}^n(-1)^{i-j}g[j]$ 。

那么 $g[i]$ 怎么算？钦定至少 $i$ 个点无用的操作相当于限定了 $i$ 个点的连边，而剩下的点可以随便连。这个用Matrix-Tree就可以算出了。

Tips

一定要看对题目。。看不对题目的话，思考或者看题解都是浪费时间！！

Code

str

发表于 2017-06-10 | 更新于 2018-06-17

Link

在考场上连看都没看。。。

Solution

Code

Lucida

It's been a while.

222 日志

127 标签

Solution

Code

Solution

Solution

跳蚤国王下江南

Solution

Tips

Code

Solution

Code

Solution

O(nnlogn)O(n\sqrt n\log n)O(n√​n​​​logn)

Solution

Tips

Code

Solution

Code

Solution

Tips

Code

Solution

Code

Solution

Code

初学

又学

然后

再学

SAM

Solution

Tips

Code

Solution

Code

$O(n\sqrt n\log n)$