一道推断题（自己编的类型）。
其实我们做过一些题后发现，有的时候不能模拟，如果我们在屏幕之外想出了这道题的实质，就可以用很简单的代码写出一道看似很复杂的题（很重要！！！）。
就以这道题为例呐：
看似没什么能头绪，其实思考后就能明白就是一个快速幂（要不是数据范围快速幂都不是）：
（orz）由于感觉洛谷题解很好，就直接拿过来了：
做法1
倒推1（可以这样蒙蔽你自己）
想要最后得到1，那么必然存在一个数ii，使得ii减去它的一个因数得到1，那么满足条件的只有2了，同理可推得只有4满足，又因为不能重复跳相同的高度，所以就有了1、2、4、8、16向上不断加的过程。
做法2
倒推2（正解）
我们可以肯定2的次方必然满足要求（一遍一遍减去一半就行），不好验证的就是剩下的数。
对于任意一个2的次方，它只是1、2、4、8...的倍数。也就是说，它不是任何一个非2方数的倍数，那么它加上这个非2方数后，也不是这个数的倍数。
根据题中规则，对于一个深度，只能跳它的因数的深度，且用过的深度不能再用，那么对于任意一个 2方数+非2方数，它一定不是这个非2方数的倍数，也就不能通过减掉这个非2方数来达到2的次方的状态。
同理，对于一个2方数+另一个2方数（2个数不等），你减一个非2方数肯定达不到2的次方的状态，转入上一段所描述的状态。
然后这个两个数的和一定是其中较小2方数的倍数（不解释），那么你需要减去这个较小数以达到2的次方的状态。
如果你减去了这个较小2方数（重点来了！），那么你在这个大的2方数不断减成1的过程中一定需要再减一遍这个较小的2方数！
用8+4举例，为12。已经知道减3、6都不会到达1（看第3段），减去2又不是2方数（10），所以减4。但8往下减小会用到一次4！所以一个2方数+另一个2方数的情况也无法满足。
2方数+另一个2方数 和 2方数+非2方数已经表示了除2方数以外的所有数，这两种情况都是不行的，所以只有2的次方满足要求。
最后k<=1e18，记得用快速幂。
奉上冗长无比的代码：
#include<cstdio> using namespace std; #define int long long const int mod=123456789; int poww(int a,int b) { int ans=1,base=a; while(b) { if(b&1) ans=ans*base%mod; base=base*base%mod; b>>=1; } return ans; } main() { int n,k; scanf("%lld",&k); int p=poww(2,k-1); printf("%lld",p%mod); return 0; }