蓝桥杯2013决赛JAVA本科B组试题分解.doc

试题一：公式求值 问题描述 　　输入n, m, k，输出下面公式的值。　　其中C_n^m是组合数，表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如下。 　　输入的第一行包含一个整数n；第二行包含一个整数m，第三行包含一个整数k。 　　计算上面公式的值，由于答案非常大，请输出这个值除以999101的余数。 313 样例输出 162 样例输入 201010 样例输出 359316 数据规模和约定 　　对于10%的数据，n≤10，k≤3；　　对于20%的数据，n≤20，k≤3；　　对于30%的数据，n≤1000，k≤5；　　对于40%的数据，n≤10^7，k≤10；　　对于60%的数据，n≤10^15，k ≤100；　　对于70%的数据，n≤10^100，k≤200；　　对于80%的数据，n≤10^500，k ≤500；　　对于100%的数据，n在十进制下不超过1000位，即1≤n10^1000，1≤k≤1000，同时0≤m≤n，k≤n。 　　999101是一个质数；　　当n位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；通过推导，可以将原式变为一个只含2^(n-i)的项和C(n,m)项的公式，然后分别求这两类公式的值，均有快速方法。最终将这些项组合起来得到答案。 import?java.math.BigInteger; import?java.util.Scanner; public?class?Main { public?static?BigInteger?lucas(BigInteger?n,BigInteger?m,BigInteger?p){ if(m.equals(BigInteger.ZERO))?return?BigInteger.ONE; return?BigInteger.valueOf(f(n.mod(p).longValue(),m.mod(p).longValue())).multiply(lucas(n.divide(p),m.divide(p),p)).mod(p); } public?static?long?f(long?n,long?m){ if(mn)?return?1; if(n==m||?m==0)?return?1; if(mn-m)?m=n-m; long?tmpi=1,tmpn=1,s1=1,s2=1,ans=1; for?(int?i?=?1;?i=m;?i++)?{ tmpi=i; tmpn=n-i+1; s1=s1*tmpi%999101; s2=s2*tmpn%999101; } ans?=?s2*pow1(s1,999099)%999101; return?ans%999101; } public?static?long?pow1(long?x,long?n)?{ if(x==1)?return?1; if?(n==0) return?1; else?{ while?((n??1)==0)?{ n=1; x=(x?*x)%999101; } } long?result?=?x%999101; n=1; while?(n!=0)?{ x=(x?*x)%999101;; if?((n??1)!=0) result?=result*x%999101; n=1; } return??result; } public?static?void?main(String[]?args)?{ Scanner?sc?=?new?Scanner(System.in); BigInteger?n?=?new?BigInteger(sc.nextLine()); BigInteger?m?=?new?BigInteger(sc.nextLine()); int?k?=?Integer.parseInt(sc.nextLine()); long?start?=?System.currentTimeMillis(); BigInteger?md?=?new?BigInteger(999101); long?Cnm=lucas(n,?m,md).longValue()%999101; long?sum?=?0; if(Cnm!=0){ int[][]?a?=?new?int[k][k]; int?h?=?1; for?(int?i?=?0;?i??k;?i++)?{ for?(int?j?=?0;?j??k;?j++)?{ if?(j?=?h) a[i][j]?=0; else?{ if?(j?==?0?||?j?==?h?-?1) a[i][j]?=?1; else?{ a[i][j]?=?(a[i?-?1][j?-