【BZOJ1965】[AHOI2005]洗牌（数论）

题面

BZOJ

洛谷

题解

考虑反过来做这个洗牌的操作，假定当前牌是第\(l\)张。

因为之前洗的时候考虑了前一半和后一半，所以根据\(l\)的奇偶性可以判定在前一半还是后一半，那么\(l/2\)就是在这一半里面在它前面的张数，这样子很容易就可以还原回去。暴力就有\(70\)分了。

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

ll n,m,l;

int main()

{

	cin>>n>>m>>l;

	while(m--)l=(l&1)?(n>>1)+(l>>1)+1:(l>>1);

	cout<<l<<endl;

	return 0;

}

那么我们现在正着考虑，当前位置是\(l\)，洗完一次之后变到哪里去了呢？

如果\(l\le n/2\)，那么是\(2l\)，如果\(l\gt n/2\)，那么是\((l-n/2)*2-1=2l-n-1\)

因为前半部分显然存在\(2l\le n\)，而后半部分显然\(2l\gt n+1\)，所以我们可以认为每次操作之后都由\(l\)位置变成了\(2l\% (n+1)\)位置。

那么进行了\(m\)次之后出现在了\(l\)位置，即：\(x*2^{m}\equiv l(mod\ n+1)\)，而\(n\)是偶数，所以必然和前面的\(2^m\)互质，所以只需要求解一个逆元就好了。

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

ll n,m,l;

ll multi(ll a,ll b){ll s=0;while(b){if(b&1)s=(s+a)%(n+1);a=(a+a)%(n+1);b>>=1;}return s;}

ll fpow(ll a,ll b){ll s=1;while(b){if(b&1)s=multi(s,a);a=multi(a,a);b>>=1;}return s;}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

	if(!b){x=1;y=0;return a;}

	ll d=exgcd(b,a%b,y,x);

	y-=a/b*x;return d;

}

ll inv(ll a,ll b)

{

	ll x,y;exgcd(a,b,x,y);

	return (x%b+b)%b;

}

int main()

{

	cin>>n>>m>>l;

	l=multi(l,inv(fpow(2,m),n+1));

	cout<<l<<endl;

	return 0;

}

upd:

压行版本

#include<iostream>

using namespace std;

#define ll long long

ll n,m,l;

ll multi(ll a,ll b){ll s=0;while(b){if(b&1)s=(s+a)%(n+1);a=(a+a)%(n+1);b>>=1;}return s;}

ll fpow(ll a,ll b){ll s=1;while(b){if(b&1)s=multi(s,a);a=multi(a,a);b>>=1;}return s;}

void exgcd(ll a,ll b,ll &x,ll &y){(!b)?(x=1,y=0):(exgcd(b,a%b,y,x),y-=a/b*x);}

ll inv(ll a,ll b){ll x,y;exgcd(a,b,x,y);return (x%b+b)%b;}

int main()

{

	cin>>n>>m>>l;

	cout<<multi(l,inv(fpow(2,m),n+1));

	return 0;

}