中国 国家集训队 互测 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; } }
近期评论