数論のモード加算演算

に質問

1つのmビットの整数、どれだけ整数nによって除去することができますか?ここで、mは15より大きくてもよい.

試験入力1 3

試験出力4

解析1

この問題は明らかにすべての状況を窮挙することはできない.数論におけるモード加算演算には、このような性質がある(乗算に対しても同じ):
(a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n
このことから,1つの数の型取り問題を2つの和を求める数の型取り問題に分割することができ,これは明らかに動的計画で解決できる問題に属する.1 mビットの整数xについては、10進数でx=x 0に分解できます.×10m−1+x1×10m−2+⋯+xm−2×10+xm−1 .その中のi−1とiビットについて,j=xi−1 mod nとすると,
(xi−1×10+xi) mod n====[(xi−1×10) mod n+xi] mod n{[(xi−1 mod n)×10] mod n+xi} mod n[(j×10) mod n+xi] mod n(j×10+xi) mod n
これにより、c[i,j]を前iビット数モードnの残数jの個数とし、原問題はc[m,0]と定義する.第i位の取値k=0〜9は、一度挙げた後の前i位残高が(j∗10+k)%nの個数であり、前i−1位残高がjの個数の積算和に等しい.再帰式は
{c[0,0]=1,c[i,j]=0,c[i,(j∗10+k)%n] +=c[i−1,j],i=0,j≠0i≠0,k=0∼9

コード1

import java.util.Scanner;

public class ModNums {
    static void solution(long[][] c, int m, int n) {
        for (int i = 0; i < n; i++) {
            c[0][i] = 0L;
        }
        c[0][0] = 1L;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 10; k++) {
                    c[i][(j * 10 + k) % n] += c[i - 1][j];
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        long[][] c = new long[m + 1][n];
        solution(c, m, n);
        System.out.println(c[m][0]);
    }
}

へんけい

1つのmビットの整数で、その中にいくつかのビットが不確定で、“X”で表して、どのくらい整数nで除去することができますか?

試験入力9999999999 X 3

試験出力4

解析2

全体的に原問題と同様に,不確定なビットだけを窮挙し,確定したビットを直接更新すればよい.

コード2

import java.util.Scanner;

public class AmbiguousNums {
    static void solution(long[][] c, String seq, int n) {
        int length = seq.length();
        for (int i = 0; i < n; i++) {
            c[0][i] = 0L;
        }
        c[0][0] = 1L;
        for (int i = 1; i <= length; i++) {
            char ch = seq.charAt(i - 1);
            for (int j = 0; j < n; j++) {
                if (ch == 'X') {
                    for (int k = 0; k < 10; k++) {
                        c[i][(j * 10 + k) % n] += c[i - 1][j];
                    }
                } else {
                    int k = ch - '0';
                    c[i][(j * 10 + k) % n] += c[i - 1][j];
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String seq = sc.next();
        int length = seq.length();
        int n = sc.nextInt();
        long[][] c = new long[length + 1][n];
        solution(c, seq, n);
        System.out.println(c[length][0]);
    }
}