跳转至

250706 模拟赛

P9906 [COCI 2023/2024 #1] Kocke

你有 \(n\) 块大小相同的正方体积木，颜色和编号依次为 \(1\sim n\)。现在，你需要在一个长度为 \(k\) 的底座上依次放下这 \(n\) 块积木。具体的，你先选择一个位置作为初始位置，将第一块积木放在底座的这个位置；然后对于 \(i\sim n\) 的每块积木，你将它放在上一块积木在底座上的左边一个位置或右边一个位置的顶端。

放完之后，可以用一个长度为 \(k\) 的序列表示这面墙：若第 \(i\) 个位置存在积木，则序列第 \(i\) 项为该位置顶端积木的颜色，否则为 \(0\)。问能得到多少种不同的序列，答案对 \(10^9+7\) 取模。

\(2\le n,k\le 5000\)

由于只取最顶端的积木，因此不难想到时光倒流。注意到数据量不大，并且墙形如一段连续的区间，考虑 dp。同时不难发现我们无需记录区间具体的位置，只需记录区间的长度即可。

注意到由于是让我们计数最后序列，而不是中间走路的方案；不难发现一种方案形如从中间开始不断向左右两端扩展。因此设 \(f_{i,j}\) 表示当前有一段长度为 \(i\) 的段，已经放了 \(j\) 块积木，最后位于区间左（右）端点的方案数（最后停在左/右端点，答案显然相同）。考虑转移：

\[ f_{i,j}\to f_{i+1,j+1}\\ f_{i,j}\to f_{i+1,j+i}\\ \]

同时我们不一定每时每刻都在扩展或者扩展的路上，还可以在区间内部进行游走。注意到游走只不会改变序列的形态和 \(j\) 的奇偶性。因此又有转移：

\[ f_{i,j}\to f_{i,j+2} \]

接下来考虑边界。由于我们认为 \(f_{i,j}\) 表示停在左端点和右端点各有 \(f_{i,j}\) 种方案，因此在 \(i=1\) 时会计算两次方案。为了减少特判，我们可以直接从 \(f_{2,2}\) 开始转移。

考虑如何求答案。注意到区间不一定要顶满 \(k\) 格，因此对区间长度 \(i\in [2,k]\) 求和。由于最终不一定会恰好停在端点处，这无法被 \(f_{i,n}\) 统计到；注意到这种情况当且仅当最终的 \(j\) 和 \(n\) 奇偶性不同，同时由于相同奇偶性的 \(j\) 都会归到最后面的 \(f_{i,n}\) 或 \(f_{i,n-1}\)，因此不停在端点处的方案就是 \(f_{i,n-1}\)。由于停在左端点和右端点各有 \(f_{i,j}\) 种方案，因此答案要乘 \(2\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#define ll long long
using namespace std;
const int N = 5010;
const int MOD = 1e9 + 7;

int n, k, ans;
int f[N][N];

#define add(a, b) a = (a + b) % MOD;

int main() {

    cin >> n >> k;

    for(int j = 2; j <= n; j += 2) f[2][j] = 1;
    for(int i = 2; i < k; i++) {
        for(int j = 1; j + 1 <= n; j++) {
            add(f[i + 1][j + 1], f[i][j]);
        }
        for(int j = 1; i + j <= n; j++) {
            add(f[i + 1][i + j], f[i][j]);
        }
        for(int j = 3; j <= n; j++) {
            add(f[i + 1][j], f[i + 1][j - 2]);
        }
    }

    for(int i = 2; i <= k; i++) {
        add(ans, 2 * (ll)(f[i][n] + f[i][n - 1]) * (k - i + 1) % MOD);
    }

    cout << ans << '\n';

    return 0;
}

P9907 [COCI 2023/2024 #1] Mostovi