algorithm - 给定长度的表达式数

Question

定义表达式如下:

1. x is an expression.
2. If S is an expression, then (S) is also an expression;
3. If S1 and S2 are expressions, then S1 + S2 and S1 - S2 are expressions.

在程序的输入中，接收到单个整数 N (0≤N≤10^6)。

程序应该打印给定长度 N 的可能表达式的数量。

例如，如果输入收到 3，则答案为 3。如果输入收到 5，则答案为 11。

因为，长度为 3 的可能表达式:

(x)
x + x
x − x

长度为 5 的可能表达式:

((x))
(x) + x
(x) − x
(x + x)
(x − x)
x + (x)
x + x + x
x + x − x
x − (x)
x − x + x
x − x − x

我立即注意到偶数的答案是 0。我认为这是显而易见的。

进一步我认为这个任务在某种程度上与加泰罗尼亚数有关，但我仍然没有找到依赖关系。

但是我设法找到了另一个依赖项。可以注意到，去掉括号，我们得到，对于每个后续 N，所有先前的表达式组合都被保存，并且新的组合添加了一个额外的 x。并且还知道x的数量等于T(不带括号)的表达式的个数可以用公式 2^(T-1)表示

以此为基础，我可以拟出一个近似公式来解决这个问题。

C(n) = 1 + 2^1 * K(2) + 2^2 * K(3) + 2^3 * K(4) + ... + 2^(T-1) 

我加 1，因为总是从一个 X 开始，您可以使用括号获得任何奇数长度的表达式。此公式中的 K 是特定数量的 x 的括号组合数。

我的问题是我不明白如何计算 K。也许我的算法从根本上是错误的。请告诉我你将如何解决类似的问题。

由于显示的答案可能非常大，因此需要将其除以数字 998244353 的余数输出

Answer 1

让我们尝试清除重复项。重新编写语法如下:

x 是一个术语

如果 E 是一个表达式，(E) 是一个术语

如果 E 是表达式而 T 是项，则 T、E + T 和 E - T 是表达式

很容易看出，这种语法与原始语法不同，它是明确的，但生成的语言相同。所以没有重复，计数表达式是一个简单的循环。

T2*N = E2*N = 0

T1 = 1(规则 1)

TN+2 = EN(规则 2)

EN = TN + 2 * Σi=1..N-1(Ei * TN-i-1)(规则 3)

这是 Haskell 中的一个简单实现。

import Data.Function.Memoize

countExpressions = e where
  e = memoize e'
  t = memoize t'

  t' :: Integer -> Integer
  t' n | n `mod` 2 == 0 = 0
       | n < 0          = 0
       | n == 1         = 1
       | otherwise      = e (n-2)

  e' :: Integer -> Integer
  e' n | n `mod` 2 == 0 = 0
       | n < 0          = 0
       | n == 1         = 1
       | otherwise      = t n + 2 * sum [ e i * t (n - i - 1) | i <- [1 .. n - 1] ]

*Main> take 100 [countExpressions n | n <- [1, 3 ..]]
[1,3,11,45,197,903,4279,20793,103049,518859,2646723,
13648869,71039373,372693519,1968801519,10463578353,55909013009,
300159426963,1618362158587,8759309660445,47574827600981,
259215937709463,1416461675464871,7760733824437545,42624971294485657,
234643073935918683,1294379445480318899,7154203054548921813,
39614015909996567325,219721391307807180831,1220631504623087926239,
6791142807106951594977,37836272668898230450209,211079263903460624841507,
1179022517498408548259307,6593381114984955663097869,
36912754633401605027088357,206872001855792377621111719,
1160541512681304496111863447,6516761034998757444607546137,
36626471726431599611696929449,206030721360035302454144967147,
1159912468318756966857440738979,6535196976312757458815954316741,
36848290359517384607151953278125,207915629812563503607757047978543,
1173964326073477816650882885177039,6632973754276801154684587715682513,
37500380783381913572612470593205809,212141771616845919130216540310379699,
1200796887336896148680723089518807003,
6800738671816200263883634106524384509,
38536889636442988510011627147957814133,
218485512042977398145305151653730733495,
1239326915845038050044360149141574744711,
7033292023264506862542551780260402287369,
39933155439917081614646297332853271801017,
226831767346925097843230333561691461750139,
1289029341311590594848983468869684443027347,
7328315284296986666986553099014741661954997,
41679447049393908306774657262565158728242749,
237143127685214808971121513395962842396893247,
1349784790811601952460270522351087362756439999,
7685617405888261934325439002849455215101480897,
43777234761479188569377997745373040369554808897,
249441399213201079760727239070884175096545449539,
1421788206273104170110597037291669679992655467467,
8106682481051245183051939164122432823777586444269,
46236952712739482726241957070796828885901144461061,
263796547500012389075991045568478200188787343127495,
1505494303546197448208798850521962465093470377432183,
8594401341045449836250073064166142787834022984924409,
49076682267607981891161581953043415914677886508708553,
280320266446131301677230031742295788501985310605678859,
1601586332840596173311408272450448001297578264810562179,
9152920896880212340077310715209390340761766765900836773,
52321432265448368603809358946760597004004263790867845069,
299162582471779686872474383492250176467899853019558029903,
1710960325747108851680526424824365839338406280753937600175,
9787572764797186502167383984306506069134859350421021098161,
56002826581256335137366888742181921098590280122851123414609,
320510558759645457373482143086535408815419978699283345323987,
1834720209915984979211273129044265378031512818645170415937979,
10504858345289618200943791787271541774952040986916342871392477,
60159086088823368309348450772511600622372897865337635945036437,
344588540948989195561108928001926915059555461632382005041456599,
1974181027670175070340010401333370259806904412143779108649862247,
11312476685452009450676967335863524401162955580619091905703510249,
64835237450752353190998763893639202715714763660580322438622510297,
371659610579497108042931462476134744077324043897111572108114056347,
2130878613169021415579487979760948662959655889894999293018136186739,
12219387028791806639024463110386114935461203436576500756744370983317,
70083509012564592934477059788362207030336587460845882812005058539869,
402028052098946215004751367738059742841646261572310549346466902214751,
2306584783353479132966538114032939468097834663308764733103440240745375,
13235901484167449474014223822407182467968500139052835055976323393184673,
75963891886881354365534841554496218362086400892829171915974126752888929,
436042729407530476306389058812416143685813823322787812176476132370649443,
2503327555668230201236190541273518077371935886971631673204479039360235947,
14373805576752430133267125003729440694156791780558721814948310153720170445]

计算这个需要几毫秒。