Code of ABC336G 16 integers (with detailed comments) in $$$O(B^3 + N)$$$ time ($$$O(B^4 + N)$$$ in the editorial)

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;

//In the following context, `ref` refers to https://oi-wiki.org/graph/matrix-tree/
//(1)There is no theorem to count Euler trail directly. Fortunately, BEST theorem
//could count the Euler circuit. Therefore, we brute force the start vertex and the terminal vertex, add an edge from
//the start and the terminal, and transform Euler trail counting into Euler circuit counting.
//(1.1)The graph should be connected as a undirected graph, if we omit the **isolation vertices** (weak-connectivity).
//A dsu is used to check this.
//(1.2)Second, for each vertex v, either indeg(v) == outdeg(v), or |indeg(v) - outdeg(v)| = 1, and the latter situation
//could happen on exactly 0 or 2 vertices. If their is no |indeg(v) - outdeg(v)| = 1 vertex v, we are counting Euler circuits, otherwise,
//there are s such that indeg(s) - outdeg(s) == 1, and t such that outdeg(t) - indeg(t) == 1, and we are counting Euler trails from
//s to t.
//The pair (Start vertex, Euler circuit) <--> (Length N+3 sequence) forms a bijection. Starting contributes three characters, while 
//the Euler circuit contributes n.
//(2)The formula ec(G) = t^{root}(G, k) \prod (deg(v) - 1)! counts equivalence classes up to cyclic isomorphism
//e.g, A->B->A and B->A->B are considered the same Euler circuit.
//The number of Euler circuits starting at v_i is 
//[Observation2]ec(G, vi) = t^{root}(G, k) deg(v_i)\prod (deg(v) - 1)!, and sum up ec(G, vi) w.r.t vi, it is exactly |E(G)|ec(G, k). It has a 
//combinatorical meaning. Each isomorphic class is counted |E(G)| times by cyclic shift.
//To count Euler trail s->t, we increase the wt[s][t]. In such case, we should count up to **equivalent class**, as within one equivalent
//class, only one of Euler trail ends up with s->t (For example, s->t->k->s, t->k->s->t, k->s->t->k, only the second one is desired).
//In the Euler trail case, the Start vertex is fixed with only one possibility, s!
//In the Euler circuit case, we should count all trails, instead of isomorphic classes only. 
//We use the Observation2 to reduce the complexity from O(B^{w+1} + N) to O(B^w + N), although it is subtle improvement since B is small.
//(3)To handle self-loops, i.e., x->x, Becareful that in the formula Lap_{ii} = D_{ii} - Wt_{ii}, Wt_{ii} > 0.
//I am used to the `fact` that Wt_{ii} = 0 is `always true` if Wt is an adjacent matrix, but in the self-loop cases, this is not true.
//For example, A<-->B<-->C
//        (two self-loops at B)
//The Lap matrix should be
//* A B C
//A 1 -1 0
//B -1 2 -1
//C 0 -1 1
//Lap_{bb} = D_{bb} - Wt_{bb} = 2 + (2self-loops at B) - (2self-loops at B) = 2.
#define ll long long
#define P 998244353
#define C 1000005
#define add(x, y) (((ll)(x)+(ll)(y))%(P))
#define sub(x, y) (((x) - (y) + (P))%(P))
#define mul(x, y) ((1ll*(x)*(y))%(P))
#define inv(x) (power((x), ((P)-2)))
#define inc(x) ((x) = add((x), 1))
#define dec(x) ((x) = sub((x), 1))
#define NO { std::cout << "0\n"; return; }

int tmpwt[8][8], tmpin[8], tmpout[8];
int f[8], fa[8];
int fac[1000007], ifac[1000007];

int power(int a, int b)
{
    int res = 1;
    while(b>0)
    {
        if(b&1)
            res = 1ll * res * a % P;
        b = b>>1;
        a = 1ll * a * a%P;
    }
    return res;
}

int find(int x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y){
    int fax = find(x), fay = find(y);
    if(fax != fay){
        fa[fax] = fay;
    }
}

int det(vector<vector<int>>&& lap){
    int m = lap.size();
    int res = 1, w = 1;
    //Gaussian Elimination
    //https://www.luogu.com.cn/problem/P7112
	for(int i = 0; i < m; i++)
	{ 
		for(int j = i+1; j < m; ++j)
		{
    		while(lap[i][i])
			{
     	    	int div = lap[j][i]/lap[i][i];
        		for(int k = i; k < m; ++k)
				{
                    lap[j][k] = sub(lap[j][k], mul(div, lap[i][k]));
        		}
        		swap(lap[i], lap[j]);
                w = w ? P - w : 0;
    		}
    		swap(lap[i], lap[j]);
            w = w ? P - w : 0;
		}
	}
	for(int i = 0; i < m; i++) res = mul(res, lap[i][i]);
	return mul(res, w);
}

int calc(vector<vector<int>>& wt, int s, int t, bool needadd=true){
    if(needadd) inc(wt[s][t]); //In the Euler trail case, we need to enclose the t->s trail by adding an edge s->t
    int m = wt.size();
    vector<vector<int>> lap(m, vector<int>(m));
    int facmul = 1;
    for(int i = 0; i < m; ++i){
        int sm = 0;
        for(int j = 0; j < m; ++j){
            if(i != j) {
                lap[i][j] = wt[i][j] == 0 ? 0 : P - wt[i][j];
                lap[i][i] = add(lap[i][i], wt[i][j]);
            }
            sm = add(sm, wt[i][j]);
        }
        facmul = mul(fac[sm-1], facmul);
    }
    //Note that the BEST lemma is using an co-factor at (i, i) for arbitrary i, for convenience
    //we use i == 0
    //We shape the matrix into
    // 1 0 0 ... 0
    // 0 R R ... R
    // 0 R R ... R
    // 0 R R ... R
    // ...
    // 0 R R ... R
    //The R part remains the same, therefore, the det of this matrix is equal to the cofactor of the original matrix at (0, 0)
    for(int i = 1; i < m; ++i) lap[0][i] = lap[i][0] = 0;
    lap[0][0] = 1; 
    int res = det(std::move(lap));
    //printf("In calc(%d %d), res==%d, facmul==%d\n", s, t, res, facmul); for(int i = 0; i < m; ++i) { for(int j = 0; j < m; ++j) printf("%d ", lap[i][j]); printf("\n");}
    if(needadd) dec(wt[s][t]);
    return mul(facmul, res);
}

void solve(){
    int ifacmul = 1;
    for(int i = 0; i < 8; ++i) fa[i] = i;
    for(int i = 0; i < 16; ++i){
        int a = i >> 1, b = i & 7;
        cin >> tmpwt[a][b];
        ifacmul = mul(ifacmul, ifac[tmpwt[a][b]]);
        tmpout[a] = add(tmpout[a], tmpwt[a][b]);
        tmpin[b] = add(tmpin[b], tmpwt[a][b]);
        if(tmpwt[a][b]) merge(a, b);
    }
    vector<int> niso;
    int s = -1, t = -1, globalfa = -1;
    for(int i = 0; i < 8; ++i){
        if(!tmpin[i] && !tmpout[i]){
            //Filtering isolated vertices
            continue;
        }
        if(globalfa == -1) globalfa = find(i);
        else if(globalfa != find(i)){
            NO; //Not connected as a undirected graph
        }
        f[niso.size()] = i;
        if(tmpin[i] > tmpout[i]){
            //First, Euler trail only allows one vertex such that indeg - tmpout == 1
            if(tmpin[i] - tmpout[i] >= 2) NO; 
            if(s != -1) NO;
            s = niso.size();
        }
        if(tmpin[i] < tmpout[i]){
            if(tmpout[i] - tmpin[i] >= 2) NO;
            if(t != -1) NO;
            t = niso.size();
        }
        niso.push_back(i);
    }
    if((s != -1 && t == -1) || (s == -1 && t != -1)) NO;
    int m = niso.size();
    //printf("SURVIVED, m==%d, s==f[%d]==%d, t==f[%d]==%d\n", m, s, f[s], t, f[t]);
    vector<vector<int>> wt(m, vector<int>(m));
    int sm = 0;
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < m; ++j){
            //Renumbering after filtering isolated vertices.
            wt[i][j] = tmpwt[f[i]][f[j]];
            sm = add(sm, wt[i][j]);
        }
    }
    int ans = 0;
    if(s != -1){
        ans = calc(wt, s, t);
    }else{
        //for(int i = 0; i < m; ++i) ans = add(ans, calc(wt, i, i)); //AC, ZLT
        ans = mul(sm, calc(wt, 0, 0, false)); //Improve using Observation 2
    }
    ans = mul(ans, ifacmul); //Remove multiple edges between two vertices i->j, as they generate the same sequences
    cout << ans << "\n";
}

int main(void){
    cin.tie(0) -> sync_with_stdio(0);
    fac[0] = ifac[0] = 1;
    for(int i = 1; i <= C; ++i){
        fac[i] = mul(i, fac[i-1]);
        ifac[i] = mul(inv(i), ifac[i-1]);
    }
    solve();
}

Why there are so few contests in the coming days? I want to compete and gamble more.

Bug or feature?

Problem: Link

Submission: Link $$$O(n)$$$, 93ms!

Part1: Hint

By looking at the $$$4$$$ test cases, we find that answers for $$$b[i] = 1$$$ are the same.

Part2: The greedy strategy (for each index $$$i$$$)

First, we define some macros for convenience:

The previous index of $$$x$$$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $$$x$$$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $$$b[x]==1$$$, rt(x) denotes the place of the next $$$1$$$ in the loop: rt(x). For example, let $$$b$$$ be an $$$1$$$-indexed array $$$[2, 1, 2, 1]$$$, then $$$rt(2)==4$$$ and $$$rt(4)==2$$$. Note that $$$rt(i)==i$$$ could happen, for example, $$$b==[2, 1, 2]$$$, then $$$rt(2)==2$$$. rt could be pre-calculated using a stack.

get(i, j): The liters of gas we need to go from $$$i$$$ to $$$j$$$, both inclusive and $$$1$$$-indexed. $$$j<i$$$ might happen since our trip is a circle. For example, if $$$a=[1, 2, 3, 4]$$$, then $$$get(1, 2)==a[1]+a[2]==1+2==3$$$ and $$$get(4, 2)==a[4]+a[1]+a[2]==4+1+2==7$$$. The $$$get$$$ function could be pre-calculated using the prefix sum.

We need to maintain an array $$$c$$$ in the algorithm. $$$c[i]$$$ denotes the minimum burbles we need to pay from the previous place $$$j$$$ where $$$b[j]==1$$$ to $$$i$$$. $$$j$$$ may be equal to $$$1$$$. For example, if $$$b==[1, 2, 1]$$$, then $$$c[3]$$$ denotes the minimum burbles we need to pay from $$$3$$$ to $$$3$$$, which is $$$a[3]$$$. $$$c[2]$$$ denotes the minimum burbles we need to pay from $$$1$$$ to $$$2$$$. Note that this $$$c$$$ is well-defined iff there's at least one $$$i$$$ such that $$$b[i]==1$$$. So we just need to output the case where all $$$b[i]$$$ equal to $$$2$$$.

//The Initialpoint
int i = initialpoint;
while(true){
    (1) If you are at the destination, which is the same as the initialpoint, goto finish.

    (2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] liters that enables you to move from i to ne(i). let i = ne(i);

    (3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop. Also, we need to calculate the array c.
    while(initialized2 || curi != rt(i)){ 
        //rt(i): The next i in this trip with b[i]==1
        //Why do we need this initialized2? Because curi before the loop is i, which may be equal to rt(i) at the beginning, in this case we still need to go into this loop!
        if(curi == initialpoint) goto finish;
        initialized2 = false;
        if(get(i, curi) <= k) c[curi] = get(i, curi);
        else c[curi] = k + 2*(get(i, curi) - k); //Buy k liters at i using k burbles and the left get(i, curi) - k liters using 2*(get(i, curi) - k) burbles.
        curi = ne(curi);
    }
}
finish:

You may worry about the line if(get(i, curi) <= k) c[curi] = get(i, curi);. In this line, if get(i, curi) <= k, we just buy get(i, curi) instead of filling all $$$k$$$ liters into the tank. You may think it would be better if we grasp the chance (that we are at some good place that $$$b[i]==1$$$) to make our tank full. But, our algorithm is correct. Whenever our algorithm is forced to buy one liter using two burbles, every other strategy needs to. If we have not met an $$$i$$$ such that $$$b[i]==1$$$ in our trip, then we can only buy one liter using two burbles, no matter what our strategy is. Otherwise, if we are forced to buy one liter using two burbles at some place $$$i$$$ where $$$b[i]==2$$$, let $$$j$$$ be the last $$$1$$$ we meet ($$$b[j]==1$$$). According to our algorithm, $$$get(j, i) > k$$$, which means our algorithm already makes the tank full at place $$$j$$$. Even if that, it still faces the lack of fuel issue at $$$i$$$ and has to pay for more expensive liter. For other strategies, the fuel amount is at most $$$k$$$ at place $$$j$$$, so it must also face the lack of liter issue at $$$i$$$, and has to pay for more expensive liter also!

When there is at least one $$$b[i]==1$$$ in the array, it would be beneficial to decompose our trip into 1222222 blocks. There is at least one block. We would discover that when our trip starts at the leading 1 of the block, it always has $$$0$$$ liter! We can prove by induction that each block only buys the fuel it needs for this block. If there is a partial incomplete block before that leading 1, e.g., it starts at 2, goes like 22212222, and now we are at the fourth place 1. According to our algorithm, when it does not meet one 1, you only pay for the fuel that is sufficient for you to go to the next place. Therefore, you won't have any fuel left. Blocks are independent of each other, and if you start at $$$1$$$, the answer would be the sum of these blocks, which is the same for each $$$i$$$ where $$$b[i]==1$$$.

Part3: The overall algorithm

First, we need to special judge the case where all $$$b[i]==2$$$. In this case, the answer for each $$$i$$$ is

$$$2\sum\limits_{i=1}^n a[i]$$$.

We need this special judge, otherwise, the array $$$c$$$ in Part 2 would be ill-defined, and the blocks in the last paragraph of Part 2 would be ambiguous.

We denote the answer for each $$$1$$$ as answer1.

What is the answer when you start at $$$i$$$ (we call the block to which $$$i$$$ is affiliated the troublesome block)? It would be:

$$$ans1 - c[j] + 2get(i, j) + c[pr(i)]$$$.

Since we don't go through the troublesome block, we need to discount the contribution of this block, which is $$$c[j]$$$ from $$$ans1$$$. To travel from $$$i$$$ to $$$j$$$, we need $$$2get(i, j)$$$ burbles for $$$get(i, j)$$$ liters of fuel. And $$$c[pr(i)]$$$ is the burbles we need to pay from the start of this block (which we don't need to know) to $$$pr(i)$$$, since we need to finish our trip at $$$pr(i)$$$.

Problem: Link

Submission: Link

Part 1: Calculate the Prefix function (next array) in $$$O(n)$$$

We can calculate the prefix function (next array) in linear time using the following code:

//next is a 0-indexed array that is initialized to zero.
//s is a 0-indexed string
for(int i = 1, j = 0; i < n; ++i){
    while(j && s[i] != s[j]) j = next[j-1];
    if(s[i] == s[j]) j++;
    next[i] = j;
}

Why is it $$$O(n)$$$? The key idea is the amortized analysis. $$$j$$$ increases $$$n$$$ times, each times increase at most $$$1$$$ (in fact $$$0$$$ or $$$1$$$, $$$0$$$ if s[i] != s[j] and $$$1$$$ if s[i] == s[j]). Therefore, $$$j$$$ increases at most $$$n$$$. Since $$$j$$$ is never a negative number (you can prove it by induction on the next array), the amount $$$j$$$ decreases $$$\leq$$$ the amount $$$j$$$ increases $$$\leq n$$$. Each times $$$j$$$ decreases at least $$$1$$$ (as $$$next[j-1] \leq j-1$$$), so $$$j$$$ decreases at most $$$n$$$ times. To sum all, $$$j$$$ increases and decreases at most $$$2n$$$ times, which is $$$O(n)$$$.

But there is a trap! We can calculate the whole next array in $$$O(n)$$$, but for a suffix of length $$$k$$$, calculating the items of the next array that corresponds with that suffix is not $$$O(k)$$$!!! In fact, the worst complexity for every suffix, even a single character, could also be $$$O(n)$$$! In fact the example is very easy to construct: aaaaa....az, the next array is:

$$$[0, 1, ..., num(a)-1, 0]$$$.

For $$$0 \leq i \leq num(a)$$$, the line j = next[j-1] executes $$$0$$$ times, and when the index comes to $$$z$$$, j = next[j-1] would execute $$$num(a)$$$ times! That means, the computational burden on the suffix could also be $$$O(n)$$$!

The GrandLisboa earns $$$100$$$ million from $$$10$$$ gamblers, it may earn $$$90$$$ million from you and $$$10$$$ million from another $$$9$$$ gamblers, that is amortization! Let's come back to this problem. When you append each suffix $$$t$$$ to the original string $$$s$$$, the complexity to handle the suffix is not $$$O(|t|)$$$, in fact the worst case is $$$O(|s|)$$$, and according to the analysis above, such suffix is very easy to construct!

Part 2: A fix

We note that most next transition is unnecessary. For example,the $$$0$$$-indexed string $$$s$$$ is ababcababa and we are now checking the last character, which is a. it is not necessary to scan abab (length=$4$) at all, because the prefix abab (s[0:4]) is followed by c while the prefix abab (s[5:9]) is followed by a. So, scan the first two characters ab is enough! Inspired by this, we define the last array:

//last[i][c]: Among 0 <= k <= i such that [0...k] is a prefix of [0,...,i] and [i-k,...,i] is a suffix of [0,...,i], the max k such that s[k+1]==c
//For example, s = "abcabaabd", last[7]['d'] = 7, last[7][c] = 1.
//s[0:1] = "ab" is a prefix of s[0:7]("abcabaab").
//s[0:1] is also a suffix of s[0:7]
//and s[1+1] = s[2] = 'c'
//The transition function: last[i][c] = (c == s[i+1] ? (next[i] >= 1 ? last[next[i]-1][c] : -1) : i);

We can easily transfer to the proper place in $$$O(1)$$$ time. Deducing last[i][*] from last[i-1][*] costs $$$O(|\alpha|)$$$ time ($$$\alpha$$$ is the alphabet), and such transition only happens $$$O(n)$$$ times, so we can fix this issue in $$$O(n |\alpha|)$$$ time.

As a newbie, what do I learn from this problem?

(1) First, carefully thinks about why the naive algorithm fails. This has been carefully analyzed in the Part $$$1$$$.

(2) Second, sometimes adding one dimension is really helpful.

(3) We should pay attention to the small constraints, they might be the breakthroughs. The "small constraints" are mostly explicit, but sometimes they are implicit and tricky. In this problem, the "lowercase Latin letters" is an implicit constraint that restricts the size of alphabet to $$$26$$$. When we work on some problems we may ignore this "implicit small constraints", which are the key factors. We may take the "lowercase Latin letters" for granted, but please note that the KMP algorithm never requires this! Here is another problem having "implicit small constraints": Diverse Substrings.

Part 3: Why don't us generalize this idea to the original KMP algorithm?

(1)The original $$$KMP$$$ algorithm is already linear and achieves the best theoretical complexity.

(2)The character set in the original $$$KMP$$$ algorithm is not restricted to the lower Latin letters. It can handle arbitrary character sets in linear time, not depending on the size of the character sets.