做行业网站赚钱,北京网站开发哪家公司好,广西桂林天气,想要个免费网站主题链接#xff1a; http://acm.hdu.edu.cn/showproblem.php?pid5187 题意#xff1a; 从1~n#xff0c;有多少种排列 使得 a1~ai 满足单调递增或者单调递减。ai~an 满足单调递增或者递减。 非常明显的组合问题 从n个数种选出i个数 剩下的数要满足单调递增或者递减或者递… 主题链接 http://acm.hdu.edu.cn/showproblem.php?pid5187 题意 从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(b1){ans (ansa)%c;b--;}b1;a(aa)%c;}return ans;
}LL quick_mod(LL a,LL b,LL c)
{LL ans 1;while(b){if(b1){ans multi(ans,a,c);b--;}b1;amulti(a,a,c);}return ans ;
}
int main()
{LL n,p;while(~scanf(%lld%lld,n,p)){if(n1){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
