思路

  • 读取n，计算出n位数可以有多少不同的组合方案（每一位都可以取0~9 共10种情况，所以能组合出10 ^ n种方案）
  • 读取m以及接下来的m个不能用作组合开头的字符串（以下称为 “非法开头” ）
  • 针对每个 “非法开头”，计算出以该非法开头的组合有多少种？
  • 从总的组合方案数（10 ^ n）中减去它们（“以该非法开头的组合有多少种”），就得到了最终答案

注意点

  • 根据第三个测试用例可以得知： “1”这个非法开头可以得到的组合方案，其实已经包含了“12”、“123”开头的组合方案
  • 因此如果不处理这种情况，就会重复减去“12”、“123”开头的组合方案的数量，导致最终结果比正确答案要小一些 alt

如何处理？

  • 先对所有的非法开头按照它们自身长度进行排序
  • 遍历排序后的非法开头数组，判断在当前这个非法开头之前是否有某个非法开头恰好是它的前缀
  • 如果没有，计算当前这个非法开头的组合方案数并从总的方案数减去它
  • 如果有，那么跳过当前这个非法开头，直接去判断下一个非法开头，以避免重复计算

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long allCount = (long)Math.pow(10,n);
        if(m == 0){
            System.out.println((long)Math.pow(10,n));
            return;
        }
        
        String[] str = new String[m];
        for (int i = 0; i < m; i++) {
            str[i] = sc.next();
        }
        
        Arrays.sort(str,(s1,s2) -> s1.length() - s2.length());

        for (int i = 0; i < m; i++) {
            boolean flag = true;
            for (int j = 0; j < i; j++) {
                if (str[i].startsWith(str[j])) {
                    flag = false;
                    break;
                }
            }
            if (flag) allCount -= (long) Math.pow(10, n - str[i].length());
        }
        System.out.println(allCount);
    }
}