[bzoj 1965] [Ahoi2005]SHUFFLE 洗牌

N张牌 (N为偶数), 初始牌面大小从1开始连续增加到N (不考虑花色), 一次洗牌: 将牌平均分成1~N/2, N/2+1~N两叠, 取第二叠的第1张作为新的第1张, 取第一叠的第1张作为新的第2张, 取第二叠的第2张作为新的第3张, 取第一叠的第2张作为新的第4张......问: M次洗牌后第L张牌是什么? (0 < 偶数N ≤ 10^10, 0 ≤ M ≤ 10^10) (没有概括题意是为了避免做法太显然我却并没捉到的尴尬......) 设表示某张牌变换次后的位置, 那么

逆变换也可以写出类似的递推式, 然而都是分段函数, 不好处理......

其实, 再看一下这个递推式

所以

那么

可以计算出是对模的逆元.

为了强行增加难度, 本题的乘法会爆unsigned long long. 一种解决方案是写个快速加 (我觉得叫快速积更贴切), 另一种解决方案见代码 (正确性确切的证明我也不清楚).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll mul(ll x, ll y, ll m)
{
	ll z = x*y - (ll)((ld)x*y/m + 1e-9)*m;
	return z<0 ? z+m : z;
}

ll fpm(ll x, ll n, ll m)
{
	ll y = 1;
	for (; n; n >>= 1, x = mul(x, x, m))
		if (n & 1)
			y = mul(y, x, m);
	return y;
}

int main()
{
	ll n, m, l;
	scanf("%lld%lld%lld", &n, &m, &l);
	printf("%lld\n", mul(l, fpm(n/2+1, m, n+1), n+1));
	return 0;
}