试题一：公式求值问题描述输入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≤n<10^1000，1≤k≤1000，同时0≤m≤n，k≤n。
提示999101是一个质数；当n位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；通过推导，可以将原式变为一个只含2^(n-i)的项和C(n,m)项的公式，然后分别求这两类公式的值，均有快速方法。
最终将这些项组合起来得到答案。
1.import java.math.BigInteger;2.import java.util.Scanner;3.public class Main4.{5.public static BigInteger lucas(BigInteger n,BigInteger m,BigInteger p){6.if(m.equals(BigInteger.ZERO)) return BigInteger.ONE;7.return BigInteger.valueOf(f(n.mod(p).longValue(),m.mod(p).longValue())).multiply(lucas(n.divide(p),m.divide(p),p)).mod(p);8.}9.10.11.public static long f(long n,long m){12.if(m>n) return 1;13.if(n==m|| m==0) return 1;14.if(m>n-m) m=n-m;15.long tmpi=1,tmpn=1,s1=1,s2=1,ans=1;16.for (int i = 1; i<=m; i++) {17.tmpi=i;18.tmpn=n-i+1;19.s1=s1*tmpi%999101;20.s2=s2*tmpn%999101;21.}22.ans = s2*pow1(s1,999099)%999101;23.return ans%999101;25.public static long pow1(long x,long n) {26.if(x==1) return 1;27.if (n==0)28.return 1;29.else {30.while ((n & 1)==0) {31.n>>=1;32.x=(x *x)%999101;33.}34.}35.long result = x%999101;36.n>>=1;37.while (n!=0) {38.x=(x *x)%999101;;39.if ((n & 1)!=0)40.result =result*x%999101;41.n>>=1;42.}43.return result;44.}45.public static void main(String[] args) {46.Scanner sc = new Scanner(System.in);47.BigInteger n = new BigInteger(sc.nextLine());48.BigInteger m = new BigInteger(sc.nextLine());49.int k = Integer.parseInt(sc.nextLine());50.long start = System.currentTimeMillis();51.BigInteger md = new BigInteger("999101");52.long Cnm=lucas(n, m,md).longValue()%999101;53.long sum = 0;54.if(Cnm!=0){55.int[][] a = new int[k][k];56.int h = 1;57.for (int i = 0; i < k; i++) {58.for (int j = 0; j < k; j++) {59.if (j >= h)60.a[i][j] =0;61.else {62.if (j == 0 || j == h - 1)63.a[i][j] = 1;64.else {65.a[i][j] = (a[i - 1][j - 1]*(h - j)+a[i - 1][j])%999101;66.}67.}69.h++;70.}71.long m1 = 1,n1 =1;72.long x=n.subtract(new BigInteger(k+"")).mod(md.subtract(BigInteger.ONE)).longValue();73.long n3 = pow1(2,x);74.for (int i = k - 1; i >= 0; i--) {75.n1=n3*pow1(2,i)%999101;76.m1 = m1*(n.subtract(new BigInteger((k - 1 - i) + "")).mod(md).longValue())%999101;77.sum = (sum+m1*a[k - 1][i]*n1)%999101;78.}79.sum = sum*Cnm%999101;80.}81.System.out.println(sum);82.long end = System.currentTimeMillis();83.}84.85.86.}试题二：九宫重排如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。
与空格子相邻的格子中的卡片可以移动到空格中。
经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。
如果无论多少步都无法到达，则输出-1。
输入格式输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式输出最少的步数，如果不存在方案，则输出-1。
样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22比较经典的搜索题，可以直接搜索或者使用双向搜索优化。
1.import java.io.*;2.import java.util.*;3.public class Main{4.static Map<String,Integer> hm1=new HashMap<String,Integer>();5.static Map<String,Integer> hm2=new HashMap<String,Integer>();6.public static void main(String args[]) throws IOException{7.BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));8.String start=bf.readLine();9.String end=bf.readLine();10.char[][] a=new char[3][3];11.char[][] b=new char[3][3];12.int c=0,x1=0,y1=0,x2=0,y2=0;13.for(int i=0;i<3;i++){14.for(int j=0;j<3;j++){15.a[i][j]=start.charAt(c);16.b[i][j]=end.charAt(c);17.c++;18.if(a[i][j]=='.'){19.x1=i;20.y1=j;21.}22.if(b[i][j]=='.'){23.x2=i;24.y2=j;25.}26.}27.}28.Node node1=new Node(0,x1,y1,a);29.Node node2=new Node(0,x2,y2,b);30.31.Queue<Node> qnode1=new LinkedList<Node>();32.Queue<Node> qnode2=new LinkedList<Node>();33.qnode1.add(node1);34.qnode2.add(node2);35.hm1.put(node1.gettu(), 0);36.hm2.put(node2.gettu(), 0);37.38.System.out.println(bfs(qnode1,qnode2));39.}40.public static int bfs(Queue<Node> q1,Queue<Node> q2){41.while(!q1.isEmpty()||!q2.isEmpty()){42.43.if(!q1.isEmpty()){44.Node node=q1.poll();45.46.int x=node.getX();47.int y=node.getY();48.if(hm2.containsKey(node.gettu())){49.return node.getSum()+hm2.get(node.gettu());50.}51.if(x>0){52.char[][] c=node.getCopy();53.c[x][y]=c[x-1][y];54.c[x-1][y]='.';55.Node node2=new Node(node.sum+1,x-1,y,c);56.String s=node2.gettu();57.if(hm2.containsKey(s)){58.return node2.getSum()+hm2.get(node2.gettu());59.}60.if(!hm1.containsKey(s)){61.hm1.put(s,node2.getSum());62.q1.add(node2);63.}64.}65.if(x<2){66.char[][] c=node.getCopy();67.c[x][y]=c[x+1][y];68.c[x+1][y]='.';69.Node node2=new Node(node.sum+1,x+1,y,c);70.String s=node2.gettu();71.if(hm2.containsKey(s)){72.return node2.getSum()+hm2.get(s);73.}74.if(!hm1.containsKey(s)){75.hm1.put(s,node2.getSum());76.q1.add(node2);77.}78.}79.if(y>0){80.char[][] c=node.getCopy();81.c[x][y]=c[x][y-1];82.c[x][y-1]='.';83.Node node2=new Node(node.sum+1,x,y-1,c);84.String s=node2.gettu();85.if(hm2.containsKey(s)){86.return node2.getSum()+hm2.get(s);87.}88.if(!hm1.containsKey(s)){89.hm1.put(s,node2.getSum());90.q1.add(node2);91.}92.}93.if(y<2){94.char[][] c=node.getCopy();95.c[x][y]=c[x][y+1];96.c[x][y+1]='.';97.Node node2=new Node(node.sum+1,x,y+1,c);98.String s=node2.gettu();99.if(hm2.containsKey(s)){100.return node2.getSum()+hm2 .get(s);101.}102.if(!hm1.containsKey(s)){103.hm1.put(s,node2.getSum()); 104.q1.add(node2);105.}106.}107.}108.if(!q2.isEmpty()){109.Node node=q2.poll();110.int x=node.getX();111.int y=node.getY();112.if(hm1.containsKey(node.gettu())){113.return node.getSum()+hm1.get(node .gettu());114.}115.if(x>0){116.char[][] c=node.getCopy();117.c[x][y]=c[x-1][y];118.c[x-1][y]='.';119.Node node2=new Node(node.sum+1,x -1,y,c);120.String s=node2.gettu();121.if(hm1.containsKey(s)){122.return node2.getSum()+hm1 .get(s);123.}124.if(!hm2.containsKey(s)){125.hm2.put(s,node2.getSum()); 126.q2.add(node2);127.}128.}129.if(x<2){130.char[][] c=node.getCopy();131.132.c[x][y]=c[x+1][y];133.c[x+1][y]='.';134.Node node2=new Node(node.sum+1,x +1,y,c);135.String s=node2.gettu();136.if(hm1.containsKey(s)){137.return node2.getSum()+hm1 .get(s);138.}139.if(!hm2.containsKey(s)){140.hm2.put(s,node2.getSum()); 141.q2.add(node2);142.}143.}144.if(y>0){145.char[][] c=node.getCopy();146.c[x][y]=c[x][y-1];147.c[x][y-1]='.';148.Node node2=new Node(node.sum+1,x ,y-1,c);149.String s=node2.gettu();150.if(hm1.containsKey(s)){151.return node2.getSum()+hm1 .get(s);152.}153.if(!hm2.containsKey(s)){154.hm2.put(s,node2.getSum()); 155.q2.add(node2);156.}157.}158.if(y<2){159.char[][] c=node.getCopy();160.c[x][y]=c[x][y+1];161.c[x][y+1]='.';162.Node node2=new Node(node.sum+1,x ,y+1,c);163.String s=node2.gettu();164.if(hm1.containsKey(s)){165.return node2.getSum()+hm1 .get(s);166.}167.if(!hm2.containsKey(s)){168.hm2.put(s,node2.getSum()); 169.q2.add(node2);170.}171.}172.}173.174.}175.176.return -1;177.}178.}179.class Node{180.int sum,x,y;181.char[][] c=null;182.public char[][] getCopy(){183.char[][] copy=new char[3][3];184.185.for(int i=0;i<3;i++){186.for(int j=0;j<3;j++){187.copy[i][j]=c[i][j];188.}189.}190.return copy;191.}192.public String gettu(){193.StringBuffer s=new StringBuffer();194.for(int i=0;i<3;i++){195.for(int j=0;j<3;j++){196.s.append(c[i][j]);197.}198.}199.return s.toString();200.}201.public Node(int sum, int x, int y, char[][] c) { 202.super();203.this.sum = sum;204.this.x = x;205.this.y = y;206.this.c = c;207.}208.public int getSum() {209.return sum;210.}211.public void setSum(int sum) {212.this.sum = sum;213.}214.public int getX() {215.return x;216.}217.public void setX(int x) {218.this.x = x;219.}220.public int getY() {221.return y;222.}223.public void setY(int y) { 224.this.y = y;225.}226.}。