主題鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=5187

題意：

從1~n，有多少種排列

使得?a1~ai?滿足單調遞增或者單調遞減。

??ai~an?滿足單調遞增或者遞減。

非常明顯的組合問題

?從n個數種選出i個數?剩下的數要滿足單調遞增或者遞減或者遞減的規律那么方式唯一

ans =?（C(N,0)+C(N,1)+......+C(N,N)） =2^N;

可是這樣的情況下?單調遞增和單調遞減算了兩遍??因此要減2

ans?= 2^n - 2;

注意n?= 1的情況?，因為n比較大?，要注意乘法溢出的情況

代碼例如以下：

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std;typedef long long LL;LL multi(LL a,LL b, LL c) {LL ans = 0;while(b){if(b&1){ans= (ans+a)%c;b--;}b>>=1;a=(a+a)%c;}return ans; }LL quick_mod(LL a,LL b,LL c) {LL ans = 1;while(b){if(b&1){ans = multi(ans,a,c);b--;}b>>=1;a=multi(a,a,c);}return ans ; } int main() {LL n,p;while(~scanf("%lld%lld",&n,&p)){if(n==1){printf("%d\n",1%p);continue;}LL ans = 2;ans = quick_mod(ans,n,p);ans =(ans - 2 + p)%p;printf("%I64d\n",ans);}return 0; }

版權聲明：本文博客原創文章，博客，未經同意，不得轉載。

轉載于:https://www.cnblogs.com/gcczhongduan/p/4714530.html

總結

以上是生活随笔為你收集整理的HDU5187 zhx#39;s contest(计数问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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