hdu 5187 高速幂高速乘法

hdu 5187 高速幂高速乘法

大家好,又见面了,我是全栈君。

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

Problem Description
As one of the most powerful brushes, zhx is required to give his juniors 



n
 problems.

zhx thinks the 



ith
 problem’s difficulty is 



i
. He wants to arrange these problems in a beautiful way.

zhx defines a sequence 



{ai}
 beautiful if there is an 



i
 that matches two rules below:

1: 



a1..ai
 are monotone decreasing or monotone increasing.

2: 



ai..an
 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.

zhx knows that the answer may be very huge, and you only need to tell him the answer module 



p
.
 


Input
Multiply test cases(less than 



1000
). Seek 



EOF
 as the end of the file.

For each case, there are two integers 



n
 and 



p
 separated by a space in a line. (



1n,p1018
)
 


Output
For each test case, output a single line indicating the answer.

 


Sample Input
   
   
2 233 3 5

 


Sample Output
   
   
2 1
Hint
In the first case, both sequence {1, 2} and {2, 1} are legal. In the second case, sequence {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} are legal, so the answer is 6 mod 5 = 1

/**
hdu 5187  高速幂高速乘法
题目大意:(转)数字1~n,按某种顺序排列。且满足下列某一个条件:(1)a1~ai递增,ai~an递减(2)a1~ai递减,ai~an递增。
      问有多少种不同的排列。
解题思路:首先是所有递减或所有递增各一种;另外就是满足上列两个条件的情况了。要想满足条件(1)那就仅仅能把最大的n放在i位置,
       共同拥有C(1,n-1)+C(2。n-1)+。。。

+C(n-2,n-1)即2^(n-1)-2;条件(2)与(1)同样,所以共同拥有(2^(n-1)-2)*2+2=2^n-2.**/#include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>using namespace std;typedef long long LL;LL n,p;LL qui_mul(LL x,LL m)///高速乘法{ LL re=0; while(m) { if(m&1) { re=(re+x)%p; } x=(x+x)%p; m>>=1; } return re;}LL qui_pow(LL a,LL n)///高速幂{ LL ret=1; LL tem=a%p; while(n) { if(n%1)ret=qui_mul(ret,temp)%p; temp=qui_mul(temp,temp)%p; n>>=1; } return ret;}int main(){ while(~scanf("%I64d%I64d",&n,&p)) { if(n==1) { if(p==1) printf("0\n"); else printf("1\n"); } printf("%I64d\n",(qui_mul(2,n)-2)%p); } return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116588.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 一分钟学习静态网页制作[通俗易懂]

    一分钟学习静态网页制作[通俗易懂]第一章静态网页制作:什么叫做HTML:超文本标记语言HTML优势:世界知名浏览器都支持Google,苹果,微软,等等……还有市场需求跨平台:1.win系统2.苹果系统3.linux系统w3c标准包涵:1.结构化标准(XHEML,XML)2.表现化标准(CSS)3.行为化标准(DOM,ECMAScript)网页的基本标签:1.标题标签:h1~h…

  • 开心农场最新外挂助手下载[通俗易懂]

    开心农场最新外挂助手下载[通俗易懂] “开心农场”辅助外挂使用说明:1.解压缩文件(本文件完全解压后只有876KB不占用多余空间)2.打开 这个图标www.vi128.com3.这时,在右下角会出现这个标志 然后双击它4.出现一个新的笔记5.在笔记主框内写上好友的名字(如果不好找也可以再加上编号)和将要成熟的作物6.写好后点击 右上角这个蓝色小闹钟的图标 7…

  • 虚拟机连不上网怎么办

    虚拟机连不上网怎么办 打开 控制面板\网络和Internet\网络和共享中心,单击更改适配器设置 2 右击本地连接,点击共享,勾选允许其他网络用户通过此计算机的Internet连接来连接(N)  文本框下选择 VMwareNetworkAdapterVMnet8 即VMwareNAT连接模式的网卡 3 右击VMwareNetworkAdapter…

  • 数据库索引的作用和长处缺点

    数据库索引的作用和长处缺点

  • 遍历map的key和value_有序的map集合

    遍历map的key和value_有序的map集合Golang map实现原理是hash map(核心元素是桶,key通过哈希算法被归入不同的bucket中),key是无序的,很多应用场景可能需要map key有序(例如交易所订单撮合),C++ 的stl map 实现了key有序,实际上是TreeMap是基于树(红黑树)的实现方式,即添加到一个有序列表,在O(log n)的复杂度内通过key值找到value,优点是空间要求低,但在时…

  • java 拦截器的作用?

    java 拦截器的作用?转载注明出处~1.拦截器都是做什么的?做的事和请求和响应有关。(比如前端的css或者一些加载的路径都会走这个拦截器)访问日志(记录访客的ip,来源),在线统计人数,字符集转换,身份验证可以不破坏你的业务逻辑在你的业务之外做一些其他事情~.过滤器(Filter):所谓过滤器顾名思义是用来过滤的,Java的过滤器能够为我们提供系统级别的过滤,也就是说,能过滤所有的web请求,…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号