tyvj P4620 一方的loli量产计画 （快速幂）

为什么我要写这道水题呢？那是因为Yi大佬也写了这题啊……

题面

非常明显，Last Order只可能跑掉一次。

更加明显的是：如果她会跑掉，跑掉的时刻一定不超过k，因为循环节的长度不会超过k。

于是，我们直接暴力做k次，然后快速幂就可以了。

时间复杂度：$O(k+logn)$。

虽然很想直接Link到卡拉斯科的博客，不过反正我在酒店也没事做，谁能告诉我纪中的OJ怎么上啊！

代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int n, k, p;
typedef long long LL;
LL Pow(LL x, int y){LL res = 1LL;for(; y > 0; y >>= 1, x = x * x % p)if(y & 1)  res = res * x % p;return res;
}
LL ans, v;
int main(){freopen("tyvj4620.in", "r", stdin);freopen("tyvj4620.out", "w", stdout);scanf("%d%d%d", &n, &k, &p);v = 2 % k;ans = 2;for(int i = 1; i <= min(n, k); i++){v = (v << 1) % k;ans = (ans << 1) % p;if(v == 1){  v --;ans = (ans - 1 + p) % p;}}ans = ans * Pow(2LL, n - k) % p;printf("%lld\n", ans);return 0;
}