[Problem proposal] counting non-decreasing path between two sequence with certain transition polynomial

[Misuki743]

Problem

Given integer sequences $A0, ..., A{N - 1}, B0, ..., B{N - 1}$, initial state $f0, ..., f{M - 1}$ and transition polynomial $g0, ..., g{K - 1}$, count the sum of weight over all integer sequence $x0, ..., x{N - 1} \text{ mod } 998244353$ satisfy

• $A_i \le x_i < B_i$

and the weight of such sequence is defined as $f_{x0} \prod\limits{i = 1}^{N - 1} g_{xi - x{i - 1}}$

Constraint

• $1 \leq N, M \leq 10^4$
• $1 \leq A_i < B_i \leq M$
• $K \leq 10$
• $0 \leq A_{i + 1} - Ai, B{i + 1} - B_i \leq 10$

Solution / Reference

https://noshi91.hatenablog.com/entry/2023/07/21/235339 (second algorithm mentioned here) https://codeforces.com/blog/entry/129027?#comment-1145554 (and we found it can actually handle both lower/upper limit constraint at the same time) https://qoj.ac/contest/1399/problem/7634 (Another direct application of such algorithm but with only lower limit)

[maspypy]

Thank you for suggesting the problem!

Regarding the suggested problem, I am unsure whether it can be considered a typical problem suitable for verifying the Library.

For the problem of counting monotonic increasing sequences that can be solved using the proposed method, there has already been a suggestion for Library Checker (although it is not yet prepared).

https://github.com/yosupo06/library-checker-problems/issues/1019

For the purpose of verifying the Library, is counting such unweighted monotonic increasing sequences insufficient?

If there is a reason why it is difficult to verify methods without a version that includes weighted transitions, I think we can consider this problem as well.

[Misuki743]

I thought the first algorithm can only handle unweighted version (to my understanding, it can only handle $\frac{1}{1-x}$) while the second one can handle more diverse transition under stricter constraint, in such case, I think it is reasonable to have a separate problem since the problems they can handle are kind of disjoint, and neither first problem can test second algorithm nor second problem can test first algorithm.

Or do I have some misunderstanding about the capability of these two algorithm? In such case, please tell me, thanks you!

[maspypy]

Thank you. I am considering adopting the problem.

I am struggling with the problem title. Currently, the following names have been proposed. Do you like any of them, or do you have any other suggestions?

• Counting Non-Decreasing Paths Between Two Sequences with a Certain Transition Polynomial
• Number of Increasing Sequences Between Two Sequences (with Transition Weights)
  • Use the name of an existing similar problem
• (Repeated) Weighted Transition with Side Boundaries

[maspypy]

@Misuki743

[Misuki743]

I think the second one is good

[maspypy]

じゃあそういうことにしましょう