zhx's contest HDU - 5187快速乘，解决乘数过大

题意：作为史上最强的刷子之一，zhx的老师让他给学弟(mei)们出n道题。 zhx认为第i道题的难度就是i。他想要让这些题目排列起来很漂亮。 zhx认为一个漂亮的序列{ai}下列两个条件均需满足。 1：a1..ai是单调递减或者单调递增的。 2：ai..an是单调递减或者单调递增的。 他想你告诉他有多少种排列是漂亮的。

因为答案很大，所以只需要输出答案模p之后的值。

整个数列单调递增和递减一共两个，然后考虑先递增后递减的情况，也就是枚举最大的那个数出现的地方，可能的位置是2---n-1，那么前i-1位的情况是C（n-1，i-1），前面确定，后面也随之确定，那么C(n-1,1)+C(n-1,2)+.....C(n-1,n-2),二项式展开，(a+b)^n=sigma(C(n,k)*a^(n-k)*b^k),令a=b=1，减去首末两项的1就是所要求的值，就是2^(n-1)-2

同理，枚举最小的那个数，

答案2^n-2

还有此题乘数太大，模数也太大，所以用快速乘，用快速的加法来算乘法，避免中间值溢出

#include <iostream> #include <cstdio> #include <ctime> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <set> #include <queue> using namespace std; typedef unsigned long long ll; const int INF=1e9+100; //const int mod=1e9+7; ll mod; ll mul(ll A, ll B) { ll ans = 0; while (B) { if (B & 1) ans = (ans + A) % mod; A = (A + A) % mod; B >>= 1; } return ans; } ll mypow(ll A, ll B) { ll ans = 1; while (B) { if (B & 1) ans = mul(ans, A); A = mul(A, A); B >>= 1; } return ans; } int main(){ //freopen("out.txt","w",stdout); ll n; while(cin>>n>>mod){ if(n==1) cout<<1%mod<<endl; else cout<<(mypow(2,n)+mod-2)%mod<<endl; } return 0; }