英文:
Number of expressions of a given length
问题
定义表达式如下：
- x 是一个表达式。
- 如果 S 是一个表达式，那么 (S) 也是一个表达式。
- 如果 S1 和 S2 是表达式，那么 S1 + S2 和 S1 - S2 也是表达式。
程序的输入是一个整数 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 的余数。
英文:
Define the expressions as follows:
> 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.
In input to the program, a single integer N (0≤N≤10^6) is received.
The program should print the number of possible expressions of a given length N.
For example, if the input receives 3, then the answer will be 3. And if the input receives 5, the answer will be 11.
Because, possible expressions of length 3:
(x)
x + x
x − x
And possible expressions of length 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
I immediately noticed that the answer to even numbers would be 0. I think this is obvious.
Further I thought that this task was somehow related to the Catalan Number, but I still didn't find the dependence.
But I managed to find another dependency. It can be noted that dropping the brackets, we get that for each subsequent N all previous combinations of expressions are saved and new ones are added with an additional x. And it is also known that the number of expressions with the amount of x equal to T (without brackets) can be expressed by the formula 2^(T-1)
Based on this, I can draw up an approximate formula for solving the problem.
C(n) = 1 + 2^1 * K(2) + 2^2 * K(3) + 2^3 * K(4) + ... + 2^(T-1)
I add 1, since always from one X you can get any expression of odd length using brackets. K in this formula is the number of combinations of brackets for a specific amount of x.
My problem is that I do not understand how to calculate K. Perhaps my algorithm is fundamentally wrong. Tell me please how you would solve a similar problem.
Since the displayed answer can be very large, it is necessary to output its remainder by dividing by the number 998244353
答案1
得分: 4
让我们尝试消除重复。按照以下方式重新构建语法：
- x 是一个术语。
- 如果 E 是一个表达式，那么 (E) 是一个术语。
- 如果 E 是一个表达式，T 是一个术语，那么 T、E + T 和 E - T 都是表达式。
很容易看出，这个语法与原始语法不同，但生成相同的语言。因此没有重复，并且计算表达式是一个直接的递归过程。
- T2N = E2N = 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,
...
(省略了很多数字)
...
14373805576752430133267125003729440694156791780558721814948310153720170445]
计算这些值只需要几毫秒。
<details>
<summary>英文:</summary>
Let's try to weed out duplicates. Reformulate the grammar as follows:
1. x is a term
2. if E is an expression, (E) is a term
3. if E is an expression and T is a term, then T, E + T and E - T are expressions
It is easy to see that this grammar, unlike the original one, is unambiguous, but generates the same language. So there are no duplicates, and counting expressions is a straightforward recurrence.
- T<sub>2*N</sub> = E<sub>2*N</sub> = 0
- T<sub>1</sub> = 1 (rule 1)
- T<sub>N+2</sub> = E<sub>N</sub> (rule 2)
- E<sub>N</sub> = T<sub>N</sub> + 2 * &Sigma;<sub>i=1..N-1</sub>(E<sub>i</sub> * T<sub>N-i-1</sub>) (rule 3)
Here's a straightforward implementation in 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]
It takes a few milliseconds to compute this.
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论