目录
BZOJ1965 洗牌题解ｃｏｄｅ
BZOJ1965 洗牌
题目传送门
题解
一道结论题，记数字\(i\)的位置为\(pos[i]\)，我们可以打表发现每一个数字在每次洗牌之后的位置是\(pos[i]*2\) \(Mod\) \((n+1)\)，然后我们假设第\(K\)次洗牌之后排在第\(L\)位的在原数列上的排名为\(X\)，那么可以得出\((X*2^k)\) \(Mod\) \((n+1)=L\)，然后２在模\((n+1)\)意义下逆元为\(n/2+1\)，于是移项可得\(x=l*(n/2+1)^m\) \(Mod\) \((n+1)\)。注意中途可能会乘爆掉，所以要用一个快速乘。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
ll n,m,p,l;
/*==================Define Area================*/
ll Mul(ll x,ll y,ll Md) {
ll res=0;
while(y) {
if(y&1) res+=x,res%=Md;
x+=x;x%=Md;
y>>=1;
}
return res;
}
ll Powe(ll x,ll y,ll Md) {
ll res=1;
while(y) {
if(y&1) res=Mul(res,x,Md),res%=Md;
x=Mul(x,x,Md);x%=Md;
y>>=1;
}
return res;
}
int main() {
read(n);read(m);read(l);
p=n/2+1;
ll ans=Powe(p,m,n+1);
ans=Mul(ans,l,n+1);
ans=(ans+(n+1))%(n+1);
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9435209.html
