hdu 5187 zhx's contest

题目分析
如果n=1,答案是1,否则答案是2n−2。
证明:ai肯定是最小的或者最大的。考虑另外的数,如果它们的位置定了的话,那么整个序列是唯一的。
那么ai是最小或者最大分别有2n−1种情况,而整个序列单调增或者单调减的情况被算了2次,所以要减2。
要注意的一点是因为p>231,所以要用快速乘法。用法与快速幂相同。如果直接乘会超过long long范围,从而wa掉。 快速幂+快速乘法

#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
typedef long long ll;

ll quickmul(ll x,ll m,ll p) //快速乘法,与快速幂相似
{
ll re=0;
while(m)
{
if(m&1)
{
re=(re+x)%p;
}
x=(x+x)%p;
m>>=1;
}
return re;
}
ll PowerMod(ll x, ll n, ll p)
{
if (n ==0)
{
return 1;
}
ll temp = PowerMod(quickmul(x , x,p), n/2, p); //递归计算(X*X)^[N/2]
if ((n &1) !=0) //判断n的奇偶性
{
temp = quickmul(temp , x, p);
}
return temp;
}
int main()
{
ll n,p;
while(scanf("%I64d %I64d",&n,&p)!=EOF)
{
if(n==1)
{
if (p==1) printf("0\n");
else printf("1\n");
}
else
printf("%I64d\n", (PowerMod(2,n,p)+p-2)%p);
}
return 0;
}

吐槽一下,在ubuntu的codeblocks中,n,p定义为全局变量,结果正确,定义在main中,结果不对,为此浪费了好多时间,欢迎大神指教!!!

上一篇:Windows-DB2 9.7安装图解


下一篇:【线段树】uoj#228. 基础数据结构练习题