題目鏈接：點擊查看

題目大意：給出一個n，現在有1~n的全排列，規定如果可以將其中一種排列分為兩部分：

a1-ai單調遞增/單調遞減

ai-an單調遞增/單調遞減

則稱這種排列為美麗的排列，現在問一共有多少種美麗排列

題目分析：先說一下，題目和代碼不太一樣的地方，就是題目的意思是兩種情況，而讀完題后我以為有四種情況，因為有單調遞減和單調遞增兩種狀態，以及前后兩個位置，顯然是2*2=4種情況，實際上是這樣的：

a1-ai單調遞增且ai-an單調遞減

a1-ai單調遞減且ai-an單調遞增

明白題意后就比較容易了，這道題目的關鍵突破點是，兩個條件中都有ai這個選項，那么如果前半段是單調遞增的，那么ai一定是最大值，同理如果前半段是單調遞減的，那么ai一定是最小值，這樣一來只需要挑若干個數分配在ai的兩側即可，單調性決定了排列方案的唯一性，那么讓ai的下標從1到n，也就是從剩下n-1個數中選取多少個數放到ai的左邊去，那么剩下的數一定放在右邊了，寫成公式的形式就是C(0,n-1)+C(1,n-1)+......C(n-2,n-1)+C(n-1,n-1)，結果是2^(n-1)，當然這只是前半段是單調遞增的情況，加上前半段是單調遞減的情況還需要乘以二，那么答案就是2^n，因為有兩種情況被計算了兩次，也就是1,2,3...n-1,n的情況和n,n-1...3,2,1被計算了兩次，所以最后答案需要減去2，也就是2^n-2

又因為這個題目的取模給到了1e18，直接乘的話會爆longlong，所以需要用到快速加配合取模，時間復雜度為logn*logn

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;LL mod;LL q_mul(LL a,LL b) {LL ans=0;while(b){if(b&1)ans=(ans+a)%mod;a=a*2%mod;b>>=1;}return ans; }LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans=q_mul(a,ans);a=q_mul(a,a);b>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);LL n;while(scanf("%lld%lld",&n,&mod)!=EOF)printf("%lld\n",(q_pow(2,n)-2+mod)%mod);return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 5187 zhx's contest(快速幂+快速加+组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。