acwing_3195_有趣的数

acwing_3195_有趣的数

//
// Created by HUAWEI on 2024/11/17.
//
#include<iostream>
#include<cstring>
#include<algorithm>#define int long longusing namespace std;const int N = 1000 + 50;
const int MOD = 1e9 + 7;
int C[N][N]; //组合数signed main() {int n;cin >> n;for (int i = 0; i <= n; i++) {for (int j = 0; j <= i; j++) {if (!j)C[i][j] = 1;else {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;}}}int res = 0;for (int k = 2; k <= n - 2; k++) {res = (res + C[n - 1][k] * (k - 1) * (n - k - 1)) % MOD;}cout << res;return 0;
}

注意事项：

• 组合数的计算方法

• 在何时取MOD

• 本题的关键在于将一个数的所有位数分为两类：0，1和2，3；然后设第一类的尾数为k，枚举k进行计算。