Số N chữ số chia hết cho 5 từ M chữ số cho trước C++

Cho N (số chữ số), mảng M chữ số. Đếm số số N chữ số (không trùng chữ số) chia hết cho 5.

Số chia hết cho 5 phải kết thúc bằng 0 hoặc 5.

Thuật toán

• Kiểm tra có 0 và/hoặc 5 trong mảng.
• Nếu có cả 2: 2 cách chọn chữ số cuối. Các vị trí còn lại: hoán vị (M-1)P(N-1).
• Nếu chỉ có 1 trong {0,5}: 1 cách chọn cuối. Hoán vị (M-1)P(N-1).
• Nếu không có 0 và 5: trả về -1.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

long long countNDivisibleBy5(int N, int M, int arr[]) {
    bool has0 = false, has5 = false;
    for (int i = 0; i < M; i++) {
        if (arr[i] == 0) has0 = true;
        if (arr[i] == 5) has5 = true;
    }
    if (!has0 && !has5) return -1;
    if (M < N) return -1;

    int waysLast = (has0 && has5) ? 2 : 1;
    long long ans = waysLast;
    int available = M - 1;
    for (int i = 1; i < N; i++) {
        ans *= available;
        available--;
    }
    return ans;
}

int main() {
    int arr[] = {5, 6, 3};
    cout << countNDivisibleBy5(2, 3, arr) << endl; // 2 (35, 65)
    return 0;
}

Kết quả

2