AtCoder Grand Contest 015
015D A or...or B Problem
题目描述
点此看题
解法
我都能想到的 \(\tt observation\) 是：我们可以去掉 \(l,r\) 二进制中相同的前缀，那么剩下的最高位 \(r\) 一定是 \(1\)，\(l\) 一定是 \(0\)，这样做的理由也很简单，就是边界是 \(2^k\) 得到的结果是易于考虑的。
那么现在的基础是两个部分 \([l,2^{id}),[2^{id},r]\)，我们考虑两边自己或的结果，以及两边联合或的结果。对于两边自己或，发现结果是 \([l,2^{id})\) 和 \([2^{id},2^{id}+2^{k})\)，其中 \(k\) 是 \(r\) 的次高位。
两边联合或的结果可以通过两边自己或的结果得出，发现就是 \([2^{id}+l,2^{id+1})\)，然后我们把这三个区间取并即可。
总结
统一形式：题目给出的是区间，那么用区间表示结果可能会得到简化。
#include
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int l,r,id,k,ans;
signed main()
{
l=read();r=read();
if(l==r) {puts("1");return 0;}
for(int i=60;i>=0;i--)
{
if((r>>i&1) && !(l>>i&1))
{id=1ll<>i&1) k=1ll<l) ans-=k-l;
printf("%lld\n",ans);
}
015F Kenus the Ancient Greek
题目描述
点此看题
解法
翻译了官方题解，补充了很多地方的证明，应该是比较严谨的中文题解了。
下文只考虑 \(i
首先考虑怎么解决第一问，考虑 \(f_0=f_1=1,f_{k}=f_{k-1}+f_{k-2}(k>1)\) 的斐波那契数列，那么迭代次数为 \(k(k>0)\) 的最小二元组一定是 \((f_{k+1},f_{k+2})\)
我们考虑缩小研究数对的范围，设 \(g(n,m)=\max_{i\leq n,j\leq m}f(i,j)\)，称 对子 \(k\) 为满足 \(f(i,j)=g(i,j)=k\) 的数对 \((i,j)\)，那么对子 \(k\) 的个数就是第二问的答案，并且只有对子才可能成为答案。
发现对子在经过少量的 \(\tt gcd\) 操作之后会快速统一形式，具体来说，构造 基对 为满足 \(i,j\leq f_{k+2}\) 的对子 \((i,j)\)，我们可以证明任意对子在一步操作之后都会变成基对：
考虑对子 \(f(x,px+y)=k+1\)，那么一步操作之后会变成基对 \(f(y,x)=k\)
使用反证法，假设 \((y,x)\) 不是基对，那么 \(x>f_{k+2}\)，而我们知道 \(f_{k+2}\leq x,f_{k+3}\leq px+y\)，这说明 \(g(x,px+y)\geq k+2\)，这和 \((x,px+y)\) 是对子矛盾，所以对子一步操作会变成基对。
由于基对被限制在了很小的范围中，所以基对的数量是很少的。可以递推地求出基对，\(k=1\) 时基对是 \((1,2),(1,3)\)，从 \(k-1\) 推到 \(k\) 时，把所有 \((x,y)\) 变成 \((y,x+y)\)，此外再增加 \((f_k,f_{k+2})\) 即可，这样求的原因是根据结论，这一层的基对只能从上一层的基对扩展而来，而又要满足 \(i,j\leq f_{k+2}\)
在计算答案的时候，我们考虑基对 \((x,y)\) 可以扩展成对子 \((x,px+y)\)，那么取出这一层的所有基对（除了最后一个，因为会算重），然后用除法即可计算扩展成多少对子，注意 \(k=1\) 需要特判。
时间复杂度 \(O(T\cdot \log n)\)
总结
统一形式需要很强的观察能力，我没有信心能自己弄出这个观察，但是保留有效状态却是可以学习的，比如本题就利用了这个技巧定义出了对子。
#include
#include
#include
using namespace std;
const int M = 1005;
#define pb push_back
#define int long long
#define pii pair
const int MOD = 1e9+7;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,k,lim,f[M];vector v[M];
void work()
{
int x=read(),y=read(),n=1,ans=0;
if(x>y) swap(x,y);
while(n+2<=k && f[n+1]<=x && f[n+2]<=y) n++;
for(pii t:v[n])
{
if(t.first<=x && t.second<=y)
ans+=(y-t.second)/t.first+1;
if(t.first<=y && t.second<=x)
ans+=(x-t.second)/t.first+1;
ans%=MOD;
}
if(n==1) ans=(ans+x)%MOD;
printf("%lld %lld\n",n,ans);
}
signed main()
{
T=read();k=1;lim=1e18;f[0]=f[1]=1;
while(f[k]+f[k-1]<=lim)
k++,f[k]=f[k-1]+f[k-2];
v[1].pb({1,2});
for(int i=2;i<=k;i++)
{
for(pii x:v[i-1])
v[i].pb({x.second,x.first+x.second});
v[i].pb({f[i+1],f[i+1]+f[i-1]});
}
while(T--) work();
}