[编程题] 分饼干

http://blog.csdn.net/wwe4023/article/details/70171648

时间限制：1秒

空间限制：32768K

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值

输入描述:

输入包括两行： 第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位) 第二行为小朋友的人数n

输出描述:

输出k可能的数值种数，保证至少为1

输入例子1:

9999999999999X 3

输出例子1:

4

测试用例:

9XXXXXXXXXXXXXXXXX 1

对应输出应该为:

100000000000000000

测试用例:

3X8XXX99X04XXXXX7X 8543

对应输出应该为:

11705428 package NeteaseSpring2017; import java.util.Scanner; public class ShareCookies3 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext())//接受多组输入 { String s=scan.nextLine(); int len=s.length(); int n=Integer.parseInt(scan.nextLine()); long[][] dp=new long[len+1][n];//dp[i][j]存储前i位余数为j的个数 dp[0][0]=1; for(int i=1;i<=len;i++)//从1开始确实方便很多，第一位可以同其他位一样处理了 { for(int j=0;j<n;j++) { char c=s.charAt(i-1);//字符串index从0开始 int y; if(c=='X') { for(int k=0;k<10;k++) { dp[i][(j*10+k)%n]+=dp[i-1][j]; } } else { dp[i][(j*10+(c-'0'))%n]+=dp[i-1][j]; //i为当前数组元素的横坐标、 //j为上一行数组元素（前i-1位对应的）纵坐标 } } } System.out.println(dp[len][0]); } scan.close(); } }