P2054 [AHOI2005] 洗牌
一道煞筆題，讓我寫了半個上午，尤其是那個垃圾樣例圖片，讓我疑惑了半天...... 還是手摸出來的。
題意概括：
一次洗牌：將一疊 \(N\)（\(N\)為偶數）張撲克牌平均分成上下兩疊，取下面一疊的第一張作為新的一疊的第一張，然后取上面一疊的第一張作為新的一疊的第二張，再取下面一疊的第二張作為新的一疊的第三張……如此交替直到所有的牌取完。
給了三個數: \(N,M,L\)。
求解洗牌 \(M\) 次，第 \(L\) 張牌是哪一個。
\(N,M \le 1\times10^{10}\)
咋做：
我們發現了這個奇葩的垃圾數據范圍，這就說明一定有什么不為人知的規律或者性質，我們開始超級手搓。
我們發現上邊的一疊很明顯：\(i\to 2i\)。
下邊的一疊比較難搞，但是我們把每一個 \(2i\) 寫出來，發現這個位置在正常的位置就是 \(\mod(n+1)\)。
然后呢？我們不會了，但是發現這個問題就是求一個未知數，我們大膽嘗試 Exgcd。
列出式子拆一下 \(\mod\) 運算。
\(2^m x + (n+1) y = L\)
就直接搞，記得用龜速乘，因為模數有可能大于 \(1e9\) 級別，所以需要這么搞，勞資調了半天沒發現。
代碼
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace Math{
int mul(int a, int b, int mod){
int sum=0;
while(b){
if(b&1) sum=(sum+a)%mod;
a=(a+a)%mod; b>>=1;}
return sum;
}
int quick_power(int a, int b, int mod){
int res=1;
while(b){
if(b&1) res=(mul(res,a,mod))%mod;
a=(mul(a,a,mod))%mod; b>>=1;}
return res;
}
int Exgcd(int a, int b, int &x, int &y){
if(!b){x=1, y=0; return a;}
int Gcd=Exgcd(b,a%b,y,x);
y-=x*(a/b); return Gcd;
}
int Gcd(int a, int b){
if(!b) return a;
return Gcd(b,a%b);
}
}
namespace BaiBaiShaFeng{
int n, m, l;
void solve(){
cin>>n>>m>>l; int a, b, x, y, Gcd;
a=Math::quick_power(2,m,n+1); b=n+1;
Gcd=Math::Exgcd(a,b,x,y);
int xlen=b/Gcd, x_0;
x_0=Math::mul(x,l/Gcd,xlen);
cout<<(x_0%xlen+xlen)%xlen<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
BaiBaiShaFeng::solve();
return 0;
}
浙公網安備 33010602011771號