日记 - 伊埃斯的博客站

你说人怎么可以蠢成这个样子

历史总是惊人的相似。我姐在高中的时候看《鬼灭之刃》而我现在也看起来了。
该说不说还挺好看。

但是现在是日记时间。

题意就是求把 $n$ 个元素分成 $k$ 个非空的不论顺序的集合的方案数。这么经典的问题当然在洛谷↗上也有，但是一看数据范围：这不对吧。

对的，他就是不对。洛谷上的题实在是太弱了，所以我们需要一个更好的做法。看到 $n,k \le 1500$ ， $\mathcal{O}(nk)$ 的做法就足够了。

设 $dp_{i,j}$ 表示将共 $i$ 个元素分成 $j$ 组的方案数。初始化是 $dp_{i,1} = 1,i \in [1,n]$ 。答案为 $dp_{n,k}$ 。考虑如何转移。对于 $dp_{i,j}$ ，我们想象有 $j$ 座塔，对应 $j$ 个集合，分配元素就是在第前几个塔上分别垒一个元素。那么有转移：

dp_{i,j} = \sum\limits_{k = 1}^{j}dp_{i - j,k}

为啥是前几个塔还有为啥是 $dp_{i - j,k}$ 而不是 $dp_{i - j,j}$ 呢？

因为题目里说的是无序，为了保证不算重复，我们就规定前一个塔放的必须比后一个塔多。那么就只能在前几个塔上放。

但是时间复杂度依然有 $\mathcal{O}(nk^2)$ ，很显然还是不行。我们考虑如何优化。用我们惊人的注意力发现：

dp_{i - 1,j - 1} = \sum\limits_{k}^{j - 1}dp_{i - j,k}

具体来说就是因为 $i - j$ 是 $i$ 和 $j$ 之间的差值，所以他俩同时 $-1$ 没有影响，再者 $k$ 是循环项，这就更没有影响了。于是我们的方程可以变成这个样子：

dp_{i,j} = dp_{i - 1,j - 1} + dp_{i - j,j}

那么这样，这道题就做完了。

可恶的 ICPC 计数 dp 不要模数，害得我还得开 __int128。

1
#include<bits/extc++.h>
2
#define int __int128
3
using namespace std;
4
const int maxn = 1505;
5
int n,k;
6
int dp[maxn][maxn];
7
inline void read(int &x)
8
{
9
    x = 0;
10
    short f = 1;
11
    char ch = getchar();
12
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
13
    while (isdigit(ch)){x = x * 10 + ch - '0'; ch = getchar();}
14
    x *= f;
15
}
16
void write(int x)
17
{
18
    if (x > 10)
19
        write(x / 10);
20
    putchar(x % 10 + '0');
21
}
22
signed main()
23
{
24
    freopen("sweets.in","r",stdin);
25
    freopen("sweets.out","w",stdout);
26
    read(n),read(k);
27
    for (int i = 1; i <= n; i++)
28
        dp[i][0] = dp[i][1] = 1;
29
    for (int i = 2; i <= k; i++)
30
        dp[0][i] = dp[1][i] = 0;
31
    for (int i = 2; i <= n; i++)
32
        for (int j = 2; j <= k; j++)
33
            dp[i][j] = dp[i - 1][j - 1] + (i > j ? dp[i - j][j] : 0);
34
    write(dp[n][k]);
35
    return 0;
36
}

Little Brackets↗

题意：对于一串合法的括号序列，定义它的深度为括号的最大嵌套层数。比如 ()() 的深度为 $1$ ，(()()) 的深度为 $2$ ，((())()) 的深度为 $3$ 。有多次询问，询问有 $n$ 对括号，深度为 $k$ 的合法括号序列数量。

设 $dp_{n,k}$ 表示有 $n$ 对括号，深度 $\le k$ 的合法括号序列数量。那么每次询问的答案就是 $dp_{n,k} - dp_{n,k - 1}$ 。初始化 $dp_{0,i} = 1$ 。转移方程如下：

dp_{i,j} = \sum\limits_{k = 1}^{i}dp_{i - k,j} \times dp_{i - 1,j - 1}

具体来说就是有两种方法以增加括号对数。一种是 ()()()...()，另一种是 (((((...)))))。分别对应两个乘数。然后这道题就做完了。可以预处理所有的 $dp$ 值，然后查询就直接算 $dp_{n,k} - dp_{n,k - 1}$ 就可以了。

注意要用高精度。

1
#include<bits/extc++.h>
2
using namespace std;
3
struct long_int
4
{
5
    int len;
6
    short d[105];
7
    long_int(int x = 0)
8
    {
9
        memset(d,0,sizeof d);
10
        len = 0;
11
        while (x)
12
        {
13
            d[++len] = x % 10;
14
            x /= 10;
15
        }
16
    }
17
    void read()
18
    {
19
        char ch = getchar();
20
        while (!isdigit(ch))ch = getchar();
21
        len = 0;
22
        while (isdigit(ch)){d[++len] = ch - '0'; ch = getchar();}
23
        reverse(d + 1,d + len + 1);
24
    }
25
    void write()
26
    {
27
        for (int i = len; i >= 1; i--)
28
            printf("%d",d[i]);
29
    }
30
    friend long_int operator+(const long_int &x,const long_int &y)
31
    {
32
        long_int ret;
33
        ret.len = max(x.len,y.len);
34
        short f = 0;
35
        for (int i = 1; i <= ret.len; i++)
36
        {
37
            ret.d[i] = x.d[i] + y.d[i] + f;
38
            if (ret.d[i] >= 10)
39
            {
40
                f = 1;
41
                ret.d[i] -= 10;
42
            }
43
            else
44
                f = 0;
45
        }
46
        if (f)
47
            ret.d[++ret.len] = f;
48
        return ret;
49
    }
50
    friend long_int operator-(const long_int &x,const long_int &y)
51
    {
52
        long_int ret;
53
        ret.len = max(x.len,y.len);
54
        short f = 0;
55
        for (int i = 1; i <= ret.len; i++)
56
        {
57
            ret.d[i] = x.d[i] - y.d[i] - f;
58
            if (ret.d[i] < 0)
59
            {
60
                f = 1;
61
                ret.d[i] += 10;
62
            }
63
            else
64
                f = 0;
65
        }
66
        while (!ret.d[ret.len])
67
            ret.len--;
68
        return ret;
69
    }
70
    friend long_int operator*(const long_int &x,const long_int &y)
71
    {
72
        long_int ret;
73
        ret.len = x.len + y.len - 1;
74
        for (int i = 1; i <= x.len; i++)
75
            for (int j = 1; j <= y.len; j++)
76
                ret.d[i + j - 1] += x.d[i] * y.d[j];
77
        for (int i = 1; i <= ret.len; i++)
78
        {
79
            ret.d[i + 1] += ret.d[i] / 10;
80
            ret.d[i] %= 10;
81
        }
82
        if (ret.d[ret.len + 1])
83
            ret.len ++;
84
        return ret;
85
    }
86
}dp[55][55];
87
void calc()
88
{
89
    for (int i = 0; i <= 50; i++)
90
        dp[0][i] = 1;
91
    for (int i = 1; i <= 50; i++)
92
        for (int j = 1; j <= 50; j++)
93
            for (int k = 1; k <= i; k++)
94
                dp[i][j] = dp[i][j] + dp[i - k][j] * dp[k - 1][j - 1];
95
}
96
signed main()
97
{
98
    freopen("brackets.in","r",stdin);
99
    freopen("brackets.out","w",stdout);
100
    calc();
101
    int t = 0,n,k;
102
    scanf("%d%d",&n,&k);
103
    while (n || k)
104
    {
105
        if (t)
106
            puts("\n");
107
        printf("Case %d: ",++t);
108
        (dp[n][k] - dp[n][k - 1]).write();
109
        scanf("%d%d",&n,&k);
110
    }
111
    return 0;
112
}

Thanks for reading!

日记

周一 2月 10 2025

1213 字 · 9 分钟

life 日记

日记

Sharing the Sweets↗

Little Brackets↗

日记