HDU5187 – zhx’s contest(快速幂+快速乘法)

题目链接:HDU5187

【题意】作为史上最强的刷子之一,zhx的老师让他给学弟(mei)们出n 道题。
zhx认为第i 道题的难度就是i 。他想要让这些题目排列起来很漂亮。
zhx认为一个漂亮的序列{a i } 下列两个条件均需满足。
1:a 1 ..a i  是单调递减或者单调递增的。
2:a i ..a n  是单调递减或者单调递增的。
他想你告诉他有多少种排列是漂亮的。
因为答案很大,所以只需要输出答案模p 之后的值。(1n,p10^18)

【分析】我写了个暴力程序,算出前面几个n发现一个规律,答案为2^n – 2;然后就是快速幂,但是还有个问题,p值有10^18,快速幂中间会出现p^2,爆了long long,所以不能直接乘,这里有两种解决方法,一种是用Java写高精度(我的C++高精度模版竟然不支持%一个LL的数),或者用快速乘法,和快速幂类似的,用加法替代乘法,则最后复杂度为O(logn*logn)

【AC CODE】46ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f;
LL n,MOD;

LL mul_mod(LL a, LL b)//a*b对MOD取余
{
    a %= MOD;
    LL ans = 0;
    while(b)
    {
        if(b&1)
        {
            ans += a;
            if(ans >= MOD) ans -= MOD;
        }
        a <<= 1;
        if(a >= MOD) a -= MOD;
        b >>= 1;
    }
    return ans;
}
LL pow_mod(LL x, LL n)
{
    LL ans = 1;
    while(n)
    {
        if(n&1) ans = mul_mod(ans,x);
        x = mul_mod(x,x);
        n >>= 1;
    }
    return ans;
}
int main()
{
#ifdef SHY
    freopen("e:\\1.txt", "r", stdin);
#endif
    while(~scanf("%I64d %I64d%*c", &n, &MOD))
    {
        if(1 == n) printf("%I64d\n", n%MOD);
        else printf("%I64d\n", (pow_mod(2,n)-2+MOD)%MOD);
    }
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码