HDU – 5187 – zhx's contest (高速幂+高速乘)

HDU – 5187 – zhx's contest (高速幂+高速乘)

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

zhx’s contest

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 448    Accepted Submission(s): 147




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

 


Source
 

思路:由题意能够求出答案为(2^n-2)%p


可是n。p都是LL型的,高速幂的时候会爆LL,所以这里要用到高速乘法,高速乘法事实上和高速幂差点儿相同。就是把乘号改为加号


注意:当n为1时。要输出1,而当p为1时要输出0。


AC代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long 
using namespace std;

LL n, p;

LL multi(LL a, LL b) {	//高速乘法。事实上和高速幂差点儿相同 
    LL ret = 0;
    while(b) {
        if(b & 1) ret = (ret + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ret;
}

LL powmod(LL a, LL b) {	//高速幂 
    LL ret = 1;
    while(b) {
        if(b & 1) ret = multi(ret, a) % p;
        a = multi(a, a) % p;
        b >>= 1;
    }
    return ret;
}


int main() {
	while(cin >> n >> p) {
		if(p == 1) {
			cout << 0 << endl;
		} else if(n == 1) {
			cout << 1 << endl;
		} else {
			LL ans = powmod(2, n) - 2;
			if(ans < 0) ans += p;
			cout << ans << endl;
		}
	}
	return 0;
}

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

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

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

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

(0)


相关推荐

  • 关于Thread.IsBackground属性的理解

    关于Thread.IsBackground属性的理解C#中,Thread类有一个IsBackground的属性.MSDN上对它的解释是:获取或设置一个值,该值指示某个线程是否为后台线程。个人感觉这样的解释等于没有解释..Net中的线程,可以分为后台线程和前台线程。后台线程与前台线程并没有本质的区别,它们之间唯一的区别就是:后台线程不会防止应用程序的进程被终止掉。呵呵,这句话读出来好像并不那么好懂.其实,说白了就是当前台线程都结束了的时候,…

    2022年10月16日
  • 递归算法时间复杂度分析[通俗易懂]

    递归算法时间复杂度分析[通俗易懂]递归算法时间复杂度分析时间复杂度:一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。T(n)=o(f(n));它表示随问题规模n的增大,算法的执行时间增长率和f(n)增长率成正比,这称作算法的渐进时间复杂度…

  • 复合主键与联合主键[通俗易懂]

    复合主键与联合主键[通俗易懂]一、复合主键 所谓的复合主键就是指你表的主键含有一个以上的字段组成,不使用无业务含义的自增id作为主键。比如 createtabletest(namevarchar(19),idnumber,valuevarchar(10),primarykey(name,id))上面的name和id字段组合起来就是你

  • CAS单点登录原理详解

    CAS单点登录原理详解1、基于Cookie的单点登录的回顾    基于Cookie的单点登录核心原理:   将用户名密码加密之后存于Cookie中,之后访问网站时在过滤器(filter)中校验用户权限,如果没有权限则从Cookie中取出用户名密码进行登录,让用户从某种意义上觉得只登录了一次。   该方式缺点就是多次传送用户名密码,增加被盗风险,以及不能跨域。同时www.qiandu.co…

  • 更新Ubuntu软件源

    更新Ubuntu软件源在Ubuntu操作系统下更换软件源,加快下载速度。

  • 《剑指offer》– 栈的压入与弹出序列、把字符串转化为整数、扑克牌顺子、孩子们的游戏(圆圈中最后剩下的数)

    《剑指offer》– 栈的压入与弹出序列、把字符串转化为整数、扑克牌顺子、孩子们的游戏(圆圈中最后剩下的数)

发表回复

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

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