P2054 [AHOI2005]洗牌

参考博客 https://www.luogu.com.cn/blog/mark---5678/solution-p2054

洗牌后的位置变换有规律

设x为初始位置

x*2^m $\equiv$ L (% n+1 )

构造一个2的逆元得：2*（ $\frac{n+1}{2}$ ） $\equiv$ 1 (% n+1 )

再进行同余等价变换得：x $\equiv$ L * (2^-1)^m(% n+1 )

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,l,mod;
ll mul(ll a,ll b){
	ll res=0;
	while(b){
		if(b&1) (res+=a)%=mod;
		b >>= 1;
		a+=a;
		a%=mod;
	}
	return res;
}
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=mul(res,a),res%=mod;
		b >>= 1;
		a=mul(a,a);
		a%=mod;
	}
	return res;
}
int main(){
	cin >> n >> m >> l;
	mod=n+1;
	ll ans=(n+2)/2;
	ans=ksm(ans,m);
	(ans=mul(ans,l))%=mod;
	cout << ans;
	return 0;
}

x*2^m $\equiv$ L (% n+1 ) 这一步还可以用扩欧求，得：

x=x0+k*(n+1)/gcd 【此题没有多个解，解是x0，

所以此题一定 x0+1*(n+1)/gcd > n+1【模数】，

别的题就不一定了，有多个解，题目会说明】

以下是打表找循环节的规律，然而并没有规律

#include<bits/stdc++.h>
using namespace std;
int n;
string str,strz[2];
int solve(int n){
	str="";strz[0]=strz[1]="";
	for(int i=1;i<=n;++i){
		str+=(i+'0');
	}
	strz[1]=str;
	int t=0,cnt=0,len=str.size()/2;
	while(1){
		//t^=1;
		cnt++;
		for(int i=0;i<len;i++){
			strz[t]+=strz[t^1][i+len];
			strz[t]+=strz[t^1][i];
		}
		if(strz[t]==str) break;
		strz[t^1]="";
		t^=1;
	}
	return cnt;
}
int main(){
	for(int i=2;i<=50;i+=2){
		printf("%3d: %d\n",i,solve(i));
	}
	return 0;
}