题解 P5042 【[国家集训队] 丢失的题面（ydc的题面）】
mrsrz
·
·
题解
窝的拿分顺序：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
---
接下来不会那么愉快了。
## 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。
输出格式和前两个点一样，那应该还是和组合数有关系。
似乎没什么特别的啊。
撕烤两个问题：上一个点，组合数为啥会带符号？组合数和什么数是一个东西？
二项式系数？把两个数带进二项式，展开后算每个项的值？
二项式定理：
$$(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：
```cpp
#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";
}
```