首页 > 其他 > 详细

BZOJ 1965 AHOI2005 SHUFFLE 洗牌 数论

时间:2014-12-30 10:05:36      阅读:153      评论:0      收藏:0      [点我收藏+]

题目大意:给定偶数张牌,问m次洗牌之后第l张牌是多少

x*2^m==l (mod n+1)
x=(n/2+1)^m*l mod n+1

快速幂+快速乘233

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD (n+1)
using namespace std;
typedef unsigned long long ll;
long long n,m,l;
ll Quick_Multiplication(ll x,ll y)
{
	ll re=0;
	while(y)
	{
		if(y&1) re+=x,re%=MOD;
		x+=x,x%=MOD;y>>=1;
	}
	return re;
}
ll Quick_Power(ll x,ll y)
{
	ll re=1;
	while(y)
	{
		if(y&1) re=Quick_Multiplication(re,x);
		x=Quick_Multiplication(x,x);y>>=1;
	}
	return re;
}
int main()
{
	cin>>n>>m>>l;
	cout<<Quick_Multiplication(Quick_Power(n/2+1,m),l)%MOD<<endl;
}


BZOJ 1965 AHOI2005 SHUFFLE 洗牌 数论

原文:http://blog.csdn.net/popoqqq/article/details/42261857

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!