计数dp+组合数学，CF 213B - Numbers

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

213B - Numbers

---

二、解题报告

1、思路分析

从0~9依次填写

对于0，如果要拿出 i 个位置填0，那么方案数为comb(n - 1, i)，因为不能有前导0

对于1，如果要拿出 j 个位置填0，那么方案数为 cnt(n - i, j)

我们发现，我们在考虑1的时候，完全不需要考虑0具体是怎么放置的

于是定义状态 f(i, j) 为 剩余 i 个位置，填写数字j, j + 1...9的方案数

那么对于 f(i, j)

如果j > 0，f(i, j) = Σ f(i - k, j + 1) * comb(i, k)

如果j == 0, f(i, j) = Σ f(i - k, j + 1) * comb(i - 1, k)

显然可以滚动数组优化

2、复杂度

时间复杂度： O(N^2 U)空间复杂度：O(N U), U = 10

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1E9 + 7;constexpr int N = 100;
int fac[N + 1], invfac[N + 1];int power(i64 a, i64 b) {int res = 1;for (; b; a = a * a % P, b >>= 1) {if (b & 1)res = res * a % P;}return res;
}auto Finit = []{fac[0] = invfac[0] = 1;for (int i = 1; i <= N; ++ i)fac[i] = 1LL * fac[i - 1] * i % P;invfac[N] = power(fac[N], P - 2);for (int i = N - 1; i; -- i)invfac[i] = (i + 1LL) * invfac[i + 1] % P;return 0;
}();int comb(int n, int m) {if (n < m) return 0;return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
}void solve(){int n;std::cin >> n;std::array<int, 10> a;for (int i = 0; i < 10; ++ i)std::cin >> a[i];std::vector<int> f(n + 1);for (int i = a[9]; i <= n; ++ i)f[i] = 1;for (int i = 8; i; -- i) {for (int j = n; ~j; -- j) {int res = 0;for (int k = a[i]; k <= j; ++ k) {res += 1LL * f[j - k] * comb(j, k) % P;if (res >= P) res -= P;}f[j] = res;}}int res = 0;for (int j = n; ~j; -- j) {for (int k = a[0]; k <= j; ++ k) {res += 1LL * f[j - k] * comb(j - 1, k) % P;if (res >= P) res -= P;		}}std::cout << res;
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main() {#ifdef DEBUGfreopen("in.txt", 'r', stdin);freopen("out.txt", 'w', stdout);#endifint t = 1;// std::cin >> t;while(t --)solve();return 0;
}