题目大意:
problem’s difficulty is. He wants to arrange these problems in a beautiful way.beautiful if there is anthat matches two rules below:are monotone decreasing or monotone increasing.are monotone decreasing or monotone increasing.He wants you to tell him that how many permutations of problems are there if the sequence of the problems’ difficulty is beautiful.
解题思路:
峰值要么是最大的要么是最小的，当峰值的位置确定之后，其他数要么在左边要么在右边共有2^(n-1)中选择，其中单调递增和单调递减两种情况算了两次要减去2.所以结果为2^n – 2；不过出题人非要把题目搞复杂来恶心人，不能用普通的乘法，，必须用快速乘法，跟快速幂差不多。
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#define LL long long using namespace std;LL mod;LL mul(LL a, LL b){LL res = 0;a %= mod;while(b){if(b & 1){res = res + a;if(res >= mod) res -= mod;}a <<= 1;if(a >= mod) a -= mod;b >>= 1;}return res;}LL Pow(LL a, LL b){LL res = 1;while(b){if(b & 1) res = mul(res, a);a = mul(a, a);b >>= 1;}return res;}int main(){LL n;while(scanf("%I64d%I64d", &n, &mod)!=EOF){if(n == 1){printf("%I64d\n", n % mod);continue;}printf("%I64d\n", (Pow(2, n) – 2 + mod)%mod);}return 0;}
这一生我只牵你的手，因为今生有你早已足够。
