A. 平滑数列
题目描述
我们定义一个正整数数列是平滑的当且仅当任意两个相邻元素的差 \(\le 1\)。
求长度为 \(N\) 的字典序第 \(K\) 小的平滑数列。
思路
首先我们做一个 \(dp\)：求出长度为 \(i\) 的首项为 \(j\) 的平滑数列数量，这里 \(j\) 只用枚举到 \(i\) 就足够了，因为 \(j>i\) 的部分等于 \(dp_{i,i}\)。
接着我们从前往后一位一位地确定。我们枚举这一位上是什么数字，如果当前是最后一个数字 \(x\) 使得第一位数字 \(\le x\) 的方案数之和 \(\ge k\)，则当前这一位显然为 \(x\)。如果枚举到了 \(N\) 还不满足，就用除法求解。并令 \(K\leftarrow K-(<x的方案数)\)。
时空复杂度均为 \(O(N^3)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 45;int n;
ll k;
__int128 dp[MAXN][MAXN][2 * MAXN], sum[MAXN][MAXN];int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> k;for(int i = 1; i <= n; ++i) {dp[i][1][i] = sum[i][1] = 1;}for(int x = 1; x <= n; ++x) {for(int i = 2; i <= n; ++i) {for(int j = 1; j <= 2 * n - 1; ++j) {dp[x][i][j] = dp[x][i - 1][j];if(j > 1) {dp[x][i][j] += dp[x][i - 1][j - 1];}if(j < 2 * n - 1) {dp[x][i][j] += dp[x][i - 1][j + 1];}sum[x][i] += dp[x][i][j];}}}k--;ll last = 0;for(int i = 1; i <= n; ++i) {ll p = 0;if(i == 1) {for(int j = 1; j < n; ++j) {if(sum[j][n - i + 1] <= k) {k -= sum[j][n - i + 1];}else {p = j;break;}}}else {for(ll j = last - 1; j <= last + 1; ++j) {if(sum[min(0ll + n, j)][n - i + 1] <= k) {k -= sum[min(0ll + n, j)][n - i + 1];}else {p = j;break;}}}if(!p) {cout << n + (ll)(k / sum[n][n - i + 1]) << " ";last = n + (ll)(k / sum[n][n - i + 1]);k %= sum[n][n - i + 1];}else {cout << p << " ";last = p;}}return 0;
}
C. 连接传送门
题目描述
给定一个字符串 \(S\)，你要构造一个排列 \(p\)，使得如果 \(p_i>i\) 那么必须满足 \(S_{p_i}=1\)。求方案数。
思路
令 \(dp_{i,j}\) 表示考虑前 \(i\) 个，其中有 \(j\) 个数的 \(p_k>i\) 且未确定的方案数。
每次转移到 \(i+1\) 时，位置 \(i+1\) 可以选择 \(p_{i+1}\le i+1或>i+1\)，并且若 \(S_{i+1}=1\)，之前还未确定的可以连向 \(i+1\)。
时空复杂度均为 \(O(N^2)\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 5005, MOD = 998244353;int t, n, dp[MAXN][MAXN];
string s;void Solve() {cin >> s;n = s.size(), s = ' ' + s;for(int i = 0; i <= n; ++i) {for(int j = 0; j <= i; ++j) {dp[i][j] = 0;}}dp[0][0] = 1;for(int i = 0; i < n; ++i) {for(int j = 0; j <= i; ++j) {dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD;dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * j % MOD) % MOD;if(s[i + 1] == '1') {dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * j % MOD) % MOD;}if(s[i + 1] == '1' && j) {dp[i + 1][j - 1] = (dp[i + 1][j - 1] + 1ll * dp[i][j] * j % MOD * j % MOD) % MOD;}}}cout << dp[n][0] << "\n";
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);for(cin >> t; t--; Solve()) {}return 0;
}
