链接 Link

150 道蓝题，是我的家乡安徽✿✿ヽ(°▽°)ノ✿

我们可以这样来看这个洗牌的过程，首先这道题只让我们求单个的一个 \(L\)，这启发我们就仅仅盯着一个数看，而不要整体变换着思考（不然压根推不出来什么东西）。

我们就盯着元素 \(1\) 看，\(n = 8\) 时，它的位置是 \((1), 2, 4, 8, 7, 5, \dots\)。

\(1, 2, 4,8\)？这简单，\(2^{m}\)。

\(7\) 又是怎么来的？\(8\times 2 = 16\)，\(16\) 怎么变成 \(7\)？\(16 - 9 = 7\)，不如说 \(16 \bmod (8+1) = 7\)。

这个时候我们就找到了规律，对于数字 \(i\)，第 \(m\) 次是 \(i2^{m}\bmod (n+1)\)。

那么我们要的就是 \(i2^{m}\equiv L \pmod {(n+1)}\)，移项得到 \(i\equiv L(2^{m})^{-1}\pmod {(n+1)}\)。

最终答案就只要算一下 \(2^{m}\) 的逆元就可以了。

大眼观察完毕，那么为什么观察出来的这个东西是对的呢？我们可以多找几个。

下面我们分情况来讨论讨论，比如在 \(m = 1\) 的情况，如果 \(i\le \dfrac{n}{2}\)，那么很显然 \(i\gets 2i\)。后半段 \(i > \dfrac{n}{2}\) 呢？那么就应该有 \(2(i - \dfrac{n}{2}) - 1 = 2i - (n+1) = 2i\bmod (n+1)\)。

对于 \(m>1\) 的情况同理。

这道题为什么我一开始不会做捏？开始我是从目标往前推，所以这时候是按照奇偶性讨论的，但是实际上肯定不能这么搞，因为题目让我们求的是 \(m\) 次变换后第 \(L\) 个，这样搞是没有前途的。其次就是抓住一个元素来研究它的下标是怎么变得，我找的就不是这个，然后就成功 GG 了。

如果你 WA11，13，那么说明你的快速幂里也要龟速乘

//SIXIANG
#include <iostream> 
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
int n, m, l;
int qmul(int n, int m, int Mod) {
	int rest = 0;
	while(m) {
		if(m & 1) rest = (rest + n) % Mod;
		n = (n + n) % Mod, m >>= 1;
	}
	return rest;
}
int qpow(int n, int m, int Mod) {
	int rest = 1;
	while(m) {
		if(m & 1) rest = qmul(rest, n, Mod);
		n = qmul(n, n, Mod), m >>= 1;
	}
	return rest;
}

int exgcd(int a, int b, int &x, int &y) {
	if(!b) {
		x = 1, y = 0;
		return a;
	}
	else {
		int rest = exgcd(b, a % b, x, y), tmp = x; 
		x = y, y = tmp - a / b * y;
		return rest;
	}
}
signed main() {
	cin >> n >> m >> l;
	
	int a = qpow(2, m, n + 1), b = n + 1, x, y;	
	int d = exgcd(a, b, x, y);
	x = (x % b + b) % b;
	cout << qmul(x, l, n + 1) << endl;
}