科大讯飞笔试

t3 dp

前置知识：
(a * b)% c = (a % c * b % c) % c
(a + b) % c = (a % c + b % c) % c

状态表示：
fij ==> 前i个字符构成的数取余p为j的方案数

状态转移：
f[i][(j * 10 % p + x % p) % p] += f[i-1][j]; 即：f[i][(j * 10 % p + x % p) % p]是由前i-1个字符构成的数取余为j的方案转移而来,即(a * 10 + b) % p,其中a为前i- 1个字符构成的数字，b为当前数字

package xunfei;

import java.io.*;
import java.util.Scanner;

public class Solution3 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static final int N = 110, M = 10010, MOD = (int) 1e9 + 7;
    static long[][] f = new long[N][M]; //fij前i和字符构成的数mod p 为j的方案数
    static int p;
    static String s;
    static char[] cs;

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        s = sc.nextLine();
        cs = s.toCharArray();
        int n = cs.length;
        p = nextInt();
        if (p == 0) out.println(0);
        else {
            if (cs[0] == '?') {
                for (int x = 0; x <= 9; x++) {
                    f[0][x % p]++;
                }
            } else {
                f[0][(cs[0] - '0') % p] = 1;
            }
            for (int i = 1; i < n; i++) {
                if (cs[i] == '?') {
                    for (int x = 0; x <= 9; x++) {
                        for (int j = 0; j < p; j++) {
                            //f[i][(int) ((f[i - 1][j] % p * x % p) % p)] += f[i - 1][j];
                            f[i][(j * 10 % p + x % p) % p] += f[i - 1][j];
                            f[i][(j * 10 % p + x % p) % p] %= MOD;
                        }
                    }
                } else {
                    int x = cs[i] - '0';
                    for (int j = 0; j < p; j++) {
                        //f[i][(int) ((f[i - 1][j] % p * x % p) % p)] += f[i - 1][j];
                        f[i][(j * 10 % p + x % p) % p] += f[i - 1][j];
                        f[i][(j * 10 % p + x % p) % p] %= MOD;
                    }
                }
            }
            out.println(f[n - 1][0]);
            out.close();
        }

    }
}