[编程题] 分饼干

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

第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)

第二行为小朋友的人数n

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

输入例子1: 9999999999999X 3

输出例子1: 4

解题思路

dp：状态转移方程dp[i][newJ] += dp[i-1][J].其中i代表数字串的长度，J代表余数，结果值代表i长度的数字串中求余n余J的所有可能结果总数。 根据以上的说明，显而易见newJ==(J*10+k)%n ，k代表当前数字串中个位的值（也就是数字串的第i位）。

import java.util.Scanner; public class Main { private static long fun(String str, int n) { long[] dp = new long[n]; char first = str.charAt(0); if (first == 'X') { for (int k = 0; k < 10; k++) { dp[k % n] = 1; } } else { int num = first - '0'; dp[num % n] = 1; } for (int i = 1; i < str.length(); i++) { long[] temp = new long[n]; char c = str.charAt(i); if (c == 'X') { for (int k = 0; k < 10; k++) { for (int j = 0; j < n; j++) { temp[(j * 10 + k) % n] += dp[j]; } } } else { int num = c - '0'; for (int j = 0; j < n; j++) { temp[(j * 10 + num) % n] += dp[j]; } } dp = temp; } return dp[0]; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int n = sc.nextInt(); System.out.println(fun(str, n)); } }