作為史上最強的刷子之一，zhx的老師讓他給學弟(mei)們出n道題，zhx認為第i道題的難度就是i，他想要讓這些題目排列起來很漂亮，
zhx認為一個漂亮的序列{ai}下列兩個條件均需滿足，
1：a1..ai是單調遞級訓者單調遞增的，
2：ai..an是單調遞級訓者單調遞增的，
他想你告訴他有多少種排列是漂亮的，因為答案很大，所以只需要輸出答案模p之后的值，
Input Multiply test cases(less than 10001000). Seek EOF as the end of the file.
Output For each case, there are two integers nn and pp separated by a space in a line. (1≤n,p≤10181≤n,p≤1018)OutputFor 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
思路：最終推導式2^n-2
因為乘數可能超long，所以用到了快速乘法
代碼：
import java.util.Scanner; public class Main { public static long multi(long a,long b,long p){//快速乘法 long ans=0; while(b>0){ if((b&1)==1) ans=(ans+a)%p; a=(a+a)%p; b>>=1; } return ans; } public static long quick_pow(long a,long b,long p){//快速冪 long ans=1; while(b>0){ if((b&1)==1) ans=multi(ans,a,p)%p; a=multi(a,a,p)%p; b>>=1; } return ans; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); while(scan.hasNext()){ long n=scan.nextLong(); long p=scan.nextLong(); if(p==1) System.out.println("0");//情況特判 else if(n==1) System.out.println("1"); else{ long ans=quick_pow(2,n,p)-2; if(ans<0) ans+=p;//注意ans為負數情況，因為快速冪計算取余-2可能小于0 System.out.println(ans); } } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/109091.html
標籤：其他