子任务 1
首先显然正面求解有点麻烦，容易想到答案就是 减去“不含有数位 的数”。
时需要算没有 的数，就是仅能用 构成数字，那显然 位数有 种， 位数有 种，。
因此答案就是 ，可以用等比数列求和，但也没有必要，注意开 long long 即可。
子任务 2:
直接纯暴力枚举即可。
#include <bits/stdc++.h>
using namespace std;
bool check(int x, int k)
{
if (x % 10 == k)
return true;
if (x / 10 > 0)
return check(x / 10, k);
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
long long R = 1;
for (int i = 1; i <= n; i++)
R *= 10;
long long ans = 0;
for (int i = 1; i <= R; i++)
if (check(i, k))
ans++;
cout << ans << "\n";
return 0;
}
子任务 3
的情况在子任务 1 就处理好了。
是子任务 3 要处理的。
这个时候有可能有同学就直接 dp 了，也确实是不太难的 dp，但其实有更简单的分类讨论即可。
有一点点特殊，因为 中含有 ，其他数字其实是多少都一样了。
这个范围中不能有 的数，其实就是 种。可以看作是 个数位每个数位都不能有 ，前面多余的前导 恰好能处理非 位数的情况。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int ten[20], nine[20];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 预处理 10^i
ten[0] = nine[0] = 1;
for (int i = 1; i <= 18; i++)
{
ten[i] = ten[i - 1] * 10;
nine[i] = nine[i - 1] * 9;
}
// work
cin >> n >> k;
int all = ten[n];
int sub = 0;
if (k == 0)
{
// 9^1+9^2+...+9^n
// 可以用等比数列求和，但没必要
for (int i = 1; i <= n; i++)
sub += nine[i];
}
else
{
if (k == 1)
sub = nine[n] - 1; // 多一个 10^n，可以少减一个
else
sub = nine[n];
}
cout << all - sub << "\n";
return 0;
}