Description 為了表彰小聯為Samuel星球的探險所做出的貢獻，小聯被邀請參加Samuel星球近距離載人探險活動。 由於Samuel星球相當遙遠，科學家們要在飛船中度過相當長的一段時間，小聯提議用撲克牌打髮長途旅行中的無聊時間。玩了幾局之後，大家覺得單純玩撲克牌對於像他們這樣的高智商人才來 ...
Submit: 989 Solved: 660
[Submit][Status][Discuss]
Description
為了表彰小聯為Samuel星球的探險所做出的貢獻，小聯被邀請參加Samuel星球近距離載人探險活動。 由於Samuel星球相當遙遠，科學家們要在飛船中度過相當長的一段時間，小聯提議用撲克牌打髮長途旅行中的無聊時間。玩了幾局之後，大家覺得單純玩撲克牌對於像他們這樣的高智商人才來說太簡單了。有人提出了撲克牌的一種新的玩法。 對於撲克牌的一次洗牌是這樣定義的，將一疊N（N為偶數）張撲克牌平均分成上下兩疊，取下麵一疊的第一張作為新的一疊的第一張，然後取上面一疊的第一張作為新的一疊的第二張，再取下麵一疊的第二張作為新的一疊的第三張……如此交替直到所有的牌取完。 如果對一疊6張的撲克牌1 2 3 4 5 6，進行一次洗牌的過程如下圖所示：
從圖中可以看出經過一次洗牌，序列1 2 3 4 5 6變為4 1 5 2 6 3。當然，再對得到的序列進行一次洗牌，又會變為2 4 6 1 3 5。 游戲是這樣的，如果給定長度為N的一疊撲克牌，並且牌面大小從1開始連續增加到N（不考慮花色），對這樣的一疊撲克牌，進行M次洗牌。最先說出經過洗牌後的撲克牌序列中第L張撲克牌的牌面大小是多少的科學家得勝。小聯想贏取游戲的勝利，你能幫助他嗎？
Input
有三個用空格間隔的整數，分別表示N，M，L （其中0＜ N ≤ 10 ^ 10 ，0 ≤ M ≤ 10^ 10，且N為偶數）。Output
單行輸出指定的撲克牌的牌面大小。Sample Input
6 2 3Sample Output
6HINT
Source
非常巧妙的一道題、
通過找規律不難發現，第$i$個位置下一輪的位置為$2i \pmod {n + 1}$
那麼下$m$輪的位置為$2^m i \pmod {n + 1}$
我們需要找到一個位置$x$，使得$2^m x \equiv L \pmod {n + 1}$
那麼$x \equiv L * 2^{-x} \pmod {n + 1}$
做完了。。
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<iostream> #define int long long inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int x, y, N, M, L, mod; int fastpow(int a, int p) { int base = 1; while(p) { if(p & 1) base = (base * a) % mod; a = (a * a) % mod; p >>= 1; } return base % mod; } int exgcd(int a, int b, int &x, int &y) { if(b == 0) {x =1; y = 0; return a;} int r = exgcd(b, a % b, x, y); int t = x; x = y; y = t -(a / b) * y; return r; } int inv(int a, int b) { exgcd(a, b, x, y); while(x < 0) x += b; return x % b; } main() { N = read(); M = read(); L = read(); mod = N + 1; printf("%lld", L % mod * inv(fastpow(2, M), mod) % mod); }
