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