P2054 [AHOI2005]洗牌
洗牌后的位置变换有规律
设x为初始位置
x*2m 
L (% n+1 )
构造一个2的逆元 得 ：2*（
） 1 (% n+1 )
再进行同余等价变换得 ：x 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=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;
}
安克创新 Anker公司福利 327人发布
