算法提高 組合公式求值 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB問題描述給定n, m，求：輸入格式輸入一行，包含兩個(gè)整數(shù)n, m。輸出格式輸出一行，包含求得的值，由于答案可能非常大，請輸出此公式除以987654321的余數(shù)。樣例輸入3 1樣例輸出162數(shù)據(jù)規(guī)模和約定1<=m<=n<=10^7。 package com.sihai.improve;import java.math.BigInteger; import java.util.Scanner; class Number { long x,y,dd; /** * @param x * @param y * @param dd */ public Number(long x, long y, long dd) { super(); this.x = x; this.y = y; this.dd = dd; } public Number() { super(); } } public class Main { static BigInteger n, m; static int k; static long monum = 999101; static BigInteger mobig = new BigInteger("999101"); static BigInteger big2 = new BigInteger("2"); static long ansnum1,ans; static long dp[][], bignum[], subnum[]; static long fact[]; private static Number gcd(long a,long b) { if (b==0) return new Number(1,0,a); Number number=gcd(b, a%b); long x=number.y; long y=number.x-(a/b)*number.y; long dd=number.dd; return new Number(x,y,dd); } private static long mod_inverse(long num) { if (num==0) return 0; Number number=gcd(num, monum); long x=(number.x+monum)%monum; return x; } private static long cal(BigInteger num) { if (num.equals(BigInteger.ZERO)) return 1; if (num.equals(BigInteger.ONE)) return 2; long mnum = cal(num.divide(big2)); mnum = mnum*mnum%monum; BigInteger mo = num.mod(big2); if (mo.equals(BigInteger.ONE)) mnum=mnum*2%monum; return mnum; } private static void init() { fact = new long[(int) (monum + 1)]; fact[0] = 1; for (int i = 1; i <= monum; i++) fact[i]=(fact[i-1]*(long)i)%monum; } private static long calc(int n,int m) { if (n<m) return 0; long mo=fact[m]*fact[n-m]%monum; long divnum=mod_inverse(mo); long res=fact[n]*divnum%monum; return res; } private static long lucas(BigInteger n,BigInteger m){ if (m.equals(BigInteger.ZERO)) return 1; int nmo=n.mod(mobig).intValue(); int mmo=m.mod(mobig).intValue(); return calc(nmo, mmo)*lucas(n.divide(mobig),m.divide(mobig))%monum; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner reader = new Scanner(System.in); n = reader.nextBigInteger(); m = reader.nextBigInteger(); k = reader.nextInt(); BigInteger kbig=new BigInteger(String.valueOf(k)); dp = new long[k + 1][k + 1]; dp[0][0]=1; long mon=n.mod(mobig).longValue(); for (int i = 0; i <= k - 1; i++) for (int j = 0; j <= i; j++) { dp[i + 1][j] = (dp[i+1][j]+(long)j*dp[i][j])%monum; dp[i + 1][j + 1] =(dp[i+1][j+1]+(long)(mon-j+monum)*dp[i][j])%monum; } long mulnum =cal(n.subtract(kbig)); for (int i = k; i >= 0; i--) { ansnum1 =(ansnum1+dp[k][i]*mulnum)%monum; mulnum = (mulnum*2)%monum; } init(); ans=ansnum1*lucas(n, m)%monum; System.out.println(ans); } }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯-组合公式求值（java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。