自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:06:29，当前版本为作者最后更新于2018-11-19 18:28:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

窝的拿分顺序：$10\rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3$。

这道题的大意是，给定输出文件，让你输出它。

观察下发的输出文件，.out文件都挺大的，不能直接输出。除了……第$10$个点。

Point 10

输入是一段英文。大概意思是你需要使得你写的程序输出自己本身。

输出也是一段英文。

emmm……这貌似是一道传统题，而且没有special judge。

那直接输出这段东西就好了o((⊙﹏⊙))o

$10$分愉快到手。

---

接下来不会那么愉快了。

Point 1

输入是$22$，输出是一个01串。

发现，串的长度刚好是$2^{22}$。

猜测和二进制、位运算有关。

仔细观察第一个字符和第二个字符，前两个字符和之后两个字符，前四个字符和之后四个字符，前八个字符和之后八个字符……

嗯！？

发现，我们取出最前面的$2^{k+1}(k\geqslant 0)$个字符，则前$2^k$个字符取反后恰好是后$2^k$个字符。

然后直接模拟即可拿到这$10$分辣~

Point 2

输入是$33$，输出还是一个01串。

串长为$3524578$。

找一下这个数有什么性质。

嗯？这东西是第$33$个斐波那契数。

那么这个点应该和斐波那契数有关。

猜测这个串也是按照类似斐波那契数的生成方式生成的。

从后往前看，每次拉一个斐波那契数长度的字符串。

容易发现，第$i$个串由第$i-2$个串和第$i-1$个串按顺序拼成（第一个为$0$，第二个为$1$）。

模拟一下即可拿到这$10$分。

Point 4

输入是$131074$个数，第一个是$131072$。

输出是$262146$个数，第一个是$262144$。

输入和输出应该有着相同的规律，且第一个数是下面的数的个数。

发现，之后第$1$个数是$1$，第二个数是$n$（$n$为第一行的数）。

看起来没什么头绪啊。

等等，把文件翻到最底下，最后一个数是$1$，倒数第二个数是$n$，然后又发现，倒数第$i$个数恰好等于第$i$个数。

也就是说，这个数列是个回文的。

啥数列是回文的，有$n+1$个元素，并且第一个、最后一个是$1$，第二个、倒数第二个是$n$呢？

跟我一起念：$1;1,2,1;1,3,3,1;\dots$

组合数！

已经猜到这个点让你干啥了，但是数列显然被取过模。我们还要求出模数是什么。

估计模数应该是个质数，而且在$10^8$左右。

那么直接把第$3$个元素算出来，对余数做差，然后把求出来的数质因数分解一下。

分出来一个大质数$104857601$。

那么直接用这个模数计算组合数即可。

验证一下，是对的。

又$10$分到手。

Point 5

输入是$262146$个数，第一个是$262144$。

输出是$131074$个数，第一个是$131072$。

发现，和上一个点的输出情况有点像啊。

不计第$1$行，第$2k-1$行都是一样的。

而且，第二行那个数很接近上面那个点的模数啊。

不难猜到，每偶数位都被取反了。

然后直接Ctrl+C，Ctrl+V一下，然后判断奇偶，输出正的或负的即可。

这$10$分还是比较容易的。

Point 6

输入是$531443$个数，第一个是$531441$。

输出是$177149$个数，第一个是$177147$。

$3$的幂次。

输出格式和前两个点一样，那应该还是和组合数有关系。

似乎没什么特别的啊。

撕烤两个问题：上一个点，组合数为啥会带符号？组合数和什么数是一个东西？

二项式系数？把两个数带进二项式，展开后算每个项的值？

二项式定理：

$$(a+b)^n=a^n+a^{n-1}b\binom{n}{2}+a^{n-2}b^2\binom{n}{3}+\dots+a^2b^{n-2}\binom{n}{n-2}+ab^{n-1}\binom{n}{n-1}+b^n $$

所以就是让你依次输出每个项的值是多少（模意义）。

那么我们得知道$a,b$分别是多少。

不是有第一项和最后一项的值吗，那就是求形如$x^{n}\equiv b\pmod p$的解。

由于前两个点模数都相同，不难猜到这个点模数还是那个数。

那么求方程的解就枚举一下即可，反正也不多。

解得$a=23333333,b=33333333$。

求出来以后，带进去算每项的值即可。

---

看一下Point 7,8,9的输入和输出的样子，不难猜到是三个图论问题，有多组询问。

Point 7

有$100000$个点，$100000$条边，$200000$个询问，图不带权。

观察输出文件，发现，要么输出0，要么就是0x7f7f7f7f。

不难想到0x7f7f7f7f代表无穷大。

这种题目显然不会让你求一些奇怪的问题，所以应该比较基础。

那么无权图，每次询问两个点，要么0要么无穷，是什么问题呢？

判断两点的连通性？

那么很简单了，写个并查集就好了。

Point 8

有$100000$个点，$99999$条边，$200000$个询问，图带权。

发现，找不到无穷大了。

那么，这应该是一棵树。

然后，观察输出文件，发现每个点的输出在输入的边权中都能找到，且都略偏大。

不难想到，题目是求两个点的路径中最长边的长度。

写个倍增即可。

Point 9

有$50000$个点，$100000$条边，$200000$个询问，图带权。

出现了无穷大，说明存在不连通的情况。

做下来你会发现，每三个点的类型都一样，所以猜测这个点和上一个点有关系。

上一个点是树，这个点是图。

那么，难道是NOIP2013货车运输？

就是询问两个点的所有路径中，经过的最大边权最小的路径的最大边权（绕死了QAQ）。

那直接跑最小生成树，然后再按上个点的方法倍增求最大边即可。

还是不难想的吧。

---

Point 3

窝觉得是最难想的一个点了，所以放在最后。

输入$12$，输出$3^{12}+11=531452$个字符，是个三进制数。

如果是每$12$个数为整体，则它并不能整除$531452$，因此应该不是这个规律。

多出$11$个数很难受啊，把前面$11$个0去掉吧。

然后再尝试把每$12$个数拉一拉，发现：

后面$10$位每$6$个数就变一次，前面$2$位变$6$次一循环。

好高兴啊！

然后你会发现，大概在第五千多个字符处，开始不同。

其实从后往前倒着看一下就可以否定掉这个规律。

怎么办啊QAQAQ？自闭吧

然后，就想着，把每个数作为开头，$12$个数拉一下。

嗯？感觉连续一段东西里面，每次都是把开头一个东西放在最后，就变成了下一个串。

当出现重复的时候，就不断加$1$，直到之前没出现过。

倒着拉了几个，好像也对啊。

那，怎么方便怎么搞吧（用string还是挺方便的，判重窝直接用unordered_set的，结果跑的巨慢），注意最前面和最后面的0需要微调一下。

终于是拿到最艰难的$10$分了。

---

前三个点窝都用string实现的，其他都比较常规。跑最慢的是第三个点。

Code：

#include<iostream>
#include<functional>
#include<algorithm>
#include<utility>
#include<unordered_set>
using namespace std;
int n;const int md=104857601;
int fac[524288],inv[524288];
inline int pow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%md)
	if(b&1)ret=1LL*ret*a%md;
	return ret;
}
inline int C(int n,int m){
	return fac[n]*1LL*inv[n-m]%md*inv[m]%md;
}
namespace subtask{
	int n,q,head[233333],cnt,fa[20][233333],mn[20][233333],dep[233333];
	struct edge{
		int to,nxt,dis;
	}e[666666];
	void dfs(int now,int pre){
		for(int i=head[now];i;i=e[i].nxt)
		if(e[i].to!=pre){
			dep[e[i].to]=dep[now]+1;
			fa[0][e[i].to]=now;
			mn[0][e[i].to]=e[i].dis;
			dfs(e[i].to,now);
		}
	}
	inline int ask(int u,int v){
		int m=0;
		if(dep[u]<dep[v])u^=v^=u^=v;
		for(int i=19;~i;--i)if(dep[fa[i][u]]>=dep[v])m=max(m,mn[i][u]),u=fa[i][u];
		if(u==v)return m;
		for(int i=19;~i;--i)
		if(fa[i][u]!=fa[i][v])m=max(m,max(mn[i][u],mn[i][v])),u=fa[i][u],v=fa[i][v];
		return max(m,max(mn[0][u],mn[0][v]));
	}
	inline void addedge(int u,int v,int t){
		e[++cnt]=(edge){v,head[u],t};head[u]=cnt;
		e[++cnt]=(edge){u,head[v],t};head[v]=cnt;
	}
	void main1(int N){
		n=N;
		cin>>q;
		for(int i=1;i<n;++i){
			int u,v,t;
			cin>>u>>v>>t;
			addedge(u,v,t);
		}
		dfs(1,0);
		for(int j=1;j<20;++j)
		for(int i=1;i<=n;++i){
			fa[j][i]=fa[j-1][fa[j-1][i]];
			mn[j][i]=max(mn[j-1][i],mn[j-1][fa[j-1][i]]);
		}
		while(q--){
			int u,v;
			cin>>u>>v;
			cout<<ask(u,v)<<'\n';
		}
	}
	pair<int,pair<int,int>>ed[233333];
	int F[233333];
	void main2(int N){
		n=N;int m,q;
		cin>>m>>q;
		for(int i=1;i<=m;++i)cin>>ed[i].second.first>>ed[i].second.second>>ed[i].first;
		sort(ed+1,ed+m+1);
		for(int i=1;i<=n;++i)F[i]=i;
		function<int(int)>find;
		find=[&find](int x){
			return x==F[x]?x:F[x]=find(F[x]);
		};
		for(int i=1;i<=m;++i)
		if(find(ed[i].second.first)!=find(ed[i].second.second)){
			F[find(ed[i].second.first)]=find(ed[i].second.second);
			addedge(ed[i].second.first,ed[i].second.second,ed[i].first);
		}
		for(int i=1;i<=n;++i)if(!dep[i])dep[i]=1,dfs(i,0);
		for(int j=1;j<20;++j)
		for(int i=1;i<=n;++i){
			fa[j][i]=fa[j-1][fa[j-1][i]];
			mn[j][i]=max(mn[j-1][i],mn[j-1][fa[j-1][i]]);
		}
		while(q--){
			int u,v;
			cin>>u>>v;
			cout<<((find(u)==find(v))?ask(u,v):0x7f7f7f7f)<<'\n';
		}
	}
};
int main(){
	for(int i=*fac=1;i<=524288;++i)fac[i]=fac[i-1]*1LL*i%md;
	inv[524288]=pow(fac[524288],md-2);
	for(int i=524287;~i;--i)inv[i]=(i+1LL)*inv[i+1]%md;
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	if(n==22){
		string ans="",out="0";
		for(int i=1;i<=1<<n;i<<=1){
			ans+=out;
			out=ans;
			for(char&it:out)it^=1;
		}
		cout<<ans<<'\n';
	}else
	if(n==33){
		string a="0",b="1",c;
		for(int i=1;i<n;++i)c=a+b,a=b,b=c;
		cout<<a<<'\n';
	}else
	if(n==12){
		unordered_set<string>st;
		string s="000000000001",output="";
		for(;;){
			output+=s[0];
			st.insert(s);
			s+=s[0];
			s.erase(0,1);
			while(st.count(s)&&s!="000000000000"){
				++s[11];
				for(int i=11;~i&&s[i]=='3';--i){
					s[i]='0';
					if(i)++s[i-1];
				}
			}
			if(s=="000000000000")break;
		}
		cout<<0<<output<<"00000000000\n";
	}else
	if(n==131072){
		cout<<"262144\n";
		for(int i=0;i<=262144;++i)
		cout<<C(262144,i)<<'\n';
	}else
	if(n==262144){
		cout<<"131072\n";
		for(int i=0;i<=131072;++i)
		cout<<((i&1)?md-C(131072,i):C(131072,i))<<'\n';
	}else
	if(n==531441){
		int a=23333333,b=33333333;
		cout<<"177147\n";
		for(int i=0;i<=177147;++i)
		cout<<1LL*C(177147,i)*pow(b,i)%md*pow(a,177147-i)%md<<'\n';
	}else
	if(n==100000){
		int m;
		cin>>m;
		if(m==n){
			static int fa[524288];
			function<int(int)>find;
			find=[&find](int x){
				return x==fa[x]?x:fa[x]=find(fa[x]);
			};
			for(int i=1;i<=n;++i)fa[i]=i;
			int q;
			cin>>q;
			for(int i=1;i<=m;++i){
				int u,v;
				cin>>u>>v;
				if(find(u)!=find(v))fa[find(u)]=find(v);
			}
			while(q--){
				int a,b;
				cin>>a>>b;
				cout<<((find(a)==find(b))?0:0x7f7f7f7f)<<'\n';
			}
		}else
		subtask::main1(n);
	}else
	if(n==50000)
	subtask::main2(n);else
	if(!n)
	cout<<"Your program should output itself here.\nSounds very difficult, yeah?\nAnyway, good luck!\n";
}