「题解」「国家集训队互测 2015」丢失的题面 lost

中国 国家集训队 互测 2015，于纪平，一个改变传统题的男人。

题目链接：Luogu P5042、UOJ 100、国家集训队互测 2015。

未完待续

题目

曾经，有一个题面摆在 ydc 的面前没有珍惜，直到失去时才后悔莫及，

如果上天再给他一次机会，ydc 一定会牢牢的记住这个题面。

没办法，已经失去了，所以这道题只能让你帮 ydc 做了。

已知的信息只有，这道题是传统题，采用全文比较的方式，时间限制 \(1\texttt{s}\)，空间限制 \(256\texttt{MB}\)。

ydc 还给你提供了这道题的所有数据。

数据下载: https://pan.baidu.com/s/1kT8Al0r 密码: cb5y

题解

思路

本题分数据点解决。

Subtask #1

观察到输入文件为一个数字 \(22\)，输出文件为
\[01101001100101101001\cdots\]
一个 \(0/1\) 串，且长度为 \(2^{22}\)，所以考虑分治法找规律。

不难发现，这个字符串是个取反回文串，并且是递归取反回文串。

例如，前四位为 \(0110\)，则 \(01\) 与 \(10\) 互反，且两个部分也符合这样的性质。

不难写出程序。

namespace Subtask1{
	bitset<1<<22> S;
	inline void Solve(void){
		S[0]=0;
		for(reg int i=0;i<n;++i){
			reg int l=(1<<i),r=(l<<1);
			for(reg int j=l;j<r;++j)
				S[j]=(!S[j-l]);
		}
		for(reg int i=0;i<(1<<22);++i)
			putchar(S[i]+'0');
		putchar('\n');
		return;
	}
}

Subtask #2

输入为 \(33\)，输出为
\[01101101011011010110101101101011011\cdots\]
长度为 \(f _ {33}\)，斐波那契数列的第 \(33\) 项。

不难发现，如果设 \(s _ 0=0,s _ 1=1\)，那么 \(s _ i=\operatorname{connect}(s _ {i-2},s _ {i-1})\)，那么答案就是 \(s _ {33}\)。

namespace Subtask2{
	string a="0",b="1",c;
	inline void Solve(void){
		for(reg int i=1;i<n;++i){
			c=a+b;
			a=b;
			b=c;
		}
		cout<<a<<endl;
		return;
	}
}

Subtask #3

太难了。

Subtask #4

不难看出是杨辉三角。

namespace Subtask4{
	const int p=104857601;
	inline int pow(reg int x,reg int exp,reg int mod){
		reg int res=1;
		while(exp){
			if(exp&1)
				res=1ll*res*x%mod;
			x=1ll*x*x%mod;
			exp>>=1;
		}
		return res;
	}
	const int MAXSIZE=524288;
	int fac[MAXSIZE],invfac[MAXSIZE];
	inline int binom(reg int n,reg int m){
		return 1ll*fac[n]*invfac[m]%p*invfac[n-m]%p;
	}
	inline void Solve(void){
		fac[0]=invfac[0]=1;
		for(reg int i=1;i<MAXSIZE;++i)
			fac[i]=1ll*fac[i-1]*i%p;
		invfac[MAXSIZE-1]=pow(fac[MAXSIZE-1],p-2,p);
		for(reg int i=MAXSIZE-2;i>=1;--i)
			invfac[i]=1ll*invfac[i+1]*(i+1)%p;
		reg int m=2*n;
		printf("%d\n",m);
		for(reg int i=0;i<=m;++i)
			printf("%d\n",binom(m,i));
		return;
	}
}

更多题目

• 「题解」「国家集训队」整数的 lqp 拆分；
• 「题解」「国家集训队」middle。