作者:书友56183408 | 来源:互联网 | 2024-11-11 12:23
这道题目是一道富有挑战性的高维计数动态规划问题。题目背景涉及科学与技术的交汇点,旨在探讨合法括号串的生成规则。具体而言,合法括号串由三种括号(()、[]、{})组成,空串被视为合法括号串。如果\(A\)是一个不包含[]和{}的合法括号串,则\((A)\)也是合法括号串。此外,如果\(A\)和\(B\)都是合法括号串,则\(AB\)也是合法括号串。该题目不仅考验了选手对动态规划的理解,还要求他们具备较强的组合数学能力,以高效地解决复杂计数问题。
一道有趣的高维计数 DP。
题目大意
定义合法的括号串为:
- 仅由
()
, []
, {}
组成;
- 空串是合法括号串;
- \(A\) 是合法括号串且不含
[]
, {}
,则 \((A)\) 是合法括号串;
- \(A\) 是合法括号串且不含
{}
,则 \([A]\) 是合法括号串;
- \(A\) 是合法括号串,则 \(\{A\}\) 是合法括号串;
- \(A,B\) 均为合法括号串,则 \(AB\) 也是合法括号串。
定义一个括号串的深度为最大的括号嵌套数,求使用了 \(L_1,L_2,L_3\) 对 {}
, []
, ()
且深度为 \(D\) 的合法括号串数量,答案对 \(11380\) 取模。
大体思路
由于 \(L_1\sim L_3,D\) 均不大,直接使用高维 DP,状态定义照抄题面。故定义 \(F(d,i,j,k)\) 表示使用了 \(i,j,k\) 对大、中、小括号且深度为 \(d\) 的数量。
状态转移自然是将当前串分割成两个串 \(TS\),使得 \(S\) 的深度为 \(d\),用某一种括号去套一个合法的串 \(T\)。由于嵌套一层后深度 \(\le d\),要求这个合法串 \(T\) 的深度不大于 \(d-1\)。
这时,我们发现需要枚举所有 \(\le d-1\) 的深度,太过麻烦,因此对 \(F\) 做前缀和处理,即将状态定义改为 \(F(d,i,j,k)\) 表示使用了 \(i,j,k\) 对大、中、小括号且深度 \(\le d\) 的数量。
对当前串 TS
,可以通过一个括号嵌套变成 (T)S
,[T]S
,{T}S
。我们可以通过枚举 \(T\) 中包含多少 {}, [], ()
,得到状态转移方程:
\[F(d,i,j,k)=
\sum_{a=0}^{i-1}\sum_{b=0}^j\sum_{c=0}^k F(d-1,a,b,c)\times F(d,i-1-a,j-b,k-c)
\\
+\sum_{b=0}^{j-1}\sum_{c=0}^k F(d-1,0,b,c)\times F(d,i,j-1-b,k-c)
\\
+\sum_{c=0}^{k-1} F(d-1,0,0,c) \times F(d,i,j,k-1-c)
\]
特殊地,对于 \(i=j=k=0\) 时,\(F(d,0,0,0)=1\)。
输出时,通过前缀和做差即可,需要特判 \(D=0\) 以及 \(L_1=L_2 = L_3 = 0\) 的情况。时间复杂度 \(O(DL^6)\)。
完整代码
#include
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair PII;
const ll mod = 11380;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c <48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template
inline void write(T x){
if(x <0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll L1, L2, L3, D, f[35][12][12][12];
int main () {
read(L1); read(L2); read(L3); read(D);
f[0][0][0][0] = 1;
rep(d, 1, D) {
f[d][0][0][0] = 1;
rep(i, 0, L1) rep(j, 0, L2) rep(k, 0, L3) {
if(!i && !j && !k) continue;
rep(a, 0, i - 1) rep(b, 0, j) rep(c, 0, k)
(f[d][i][j][k] += f[d - 1][a][b][c] * f[d][i-1 - a][j - b][k - c]) %= mod;
rep(b, 0, j - 1) rep(c, 0, k)
(f[d][i][j][k] += f[d - 1][0][b][c] * f[d][i][j-1 - b][k - c]) %= mod;
rep(c, 0, k - 1)
(f[d][i][j][k] += f[d - 1][0][0][c] * f[d][i][j][k-1 - c]) %= mod;
}
}
if(!D) writeln(((!L1 && !L2 && !L3) ? 1 : 0));
else if(!L1 && !L2 && !L3) writeln(0);
else writeln((f[D][L1][L2][L3] - f[D - 1][L1][L2][L3] + mod) % mod);
return 0;
}