Pivotal Reversal
Source: codechef
Difficulty: 2955

Pivotal Reversal
Consider performing the following operation on$S$- a binary string of length$N$:
Choose$X$such that$1 < X < N$and$S_X = 1$.
Reverse the subarray$S[X - 1, X + 1]$, i.e. effectively swapping$S_{X - 1}$and$S_{X + 1}$.
Let$T$denote another binary string of length$N$, and$f(S, T)$be the minimum number of operations to convert$S$into$T$with the above operation. If$S$cannot be covered to$T$,$f(S, T) = 0$.
Given$N$and a string$S$of length$N$, find the sum of$f(S, T)$over all$2^N$binary strings$T$of length$N$.  Since the answer may be large, print it modulo$998244353$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line contains$N$- the length of the string.
The second line contains$S$- the binary string.
Output Format
For each test case, output a single integer, the sum of$f(S, T)$over all$2^N$binary strings$T$modulo$998244353$.
Constraints$1 \le T \le 1000$$3 \le N \le 5000$$|S| = N$$S_i \in \{0, 1\}$The sum of$N$over all test cases does not exceed$5000$.
Sample 1:
Explanation:
Test Case 1
: There are$8$binary strings, out of which$6$cannot be obtained so by default their contribution is$0$.
The$2$binary strings that can be obtained are$T = 110$and$T = 011$. The first is the original string itself, so$f(S, T) = 0$. The second can be obtained by one operation at$X = 2$.
Thus, the sum is$0 \cdot 6 + 0 + 1 = 1$.
Test Case 2
: The only obtainable binary string is the original string itself, i.e.$100$and this has$f(S, T) = 0$.

Sample Input:
6
3
110
3
100
3
111
5
01101
8
11101011
13
1011101001011

Sample Output:
1
0
0
2
8
61

C++ solution:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353


#define faclim 310000

_int64 fac[faclim];
_int64 invfac[faclim];

_int64 pow1(int x,int y)
{
    int i;
    _int64 ret;
    ret=1;
    for (i=30;i>=0;i--)
    {
        ret=ret*ret%mo;
        if (((1<<i)&y)!=0) ret=ret*x%mo;
    }
    return ret;
}
_int64 inv(int x)
{
    return pow1(x,mo-2);
}
_int64 c(int x,int y)
{
    return fac[x]*invfac[y]%mo*invfac[x-y]%mo;
}
void init()
{
    int i;
    fac[0]=1;
    for (i=1;i<faclim;i++)
        fac[i]=fac[i-1]*i%mo;
    invfac[faclim-1]=inv(fac[faclim-1]);
    for (i=faclim-1;i>0;i--)
        invfac[i-1]=invfac[i]*i%mo;
}

char s[5100];

int main()
{
    int i,j,k,n,l,t,m,x,y,o,b1;
    vector<int> a;
    _int64 sum,tot,ans,cnt,diff,suml,sumr,nl,nr;
    string s1,s0;
    init();
    scanf("%d",&t);
    for (l=0;l<t;l++)
    {
        scanf("%d",&n);
        scanf("%s",s);
        ans=0;
        cnt=0;
        tot=0;
        a.clear();
        for (i=0;i<n;i++)
        {
            if (s[i]=='1') cnt++;
            else
            {
                tot+=cnt/2;
                a.push_back(cnt/2);
                cnt=0;
            }
        }
        tot+=cnt/2;
        a.push_back(cnt/2);
        sum=0;
        for (i=0;i+1<a.size();i++)
        {
            sum+=a[i];
            nl=i+1;nr=a.size()-nl;
            for (j=0;j<=tot;j++)
            {
                suml=j;sumr=tot-j;
                diff=abs(sum-j);
                //cerr<<"suml,sumr,nl,nr,diff:"<<suml<<" "<<sumr<<" "<<nl<<" "<<nr<<" "<<diff<<endl;
                ans+=diff*c(suml+nl-1,nl-1)%mo*c(sumr+nr-1,nr-1);
                ans%=mo;
                //cerr<<"ans:"<<ans<<endl;
            }
        }
        printf("%lld\n",ans);
    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const MOD = 998244353

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())

	for t := 0; t < T; t++ {
		scanner.Scan()
		N, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		S := scanner.Text()

		v := make([]int, 0)
		tot := 0
		i := 0
		for i < N {
			j := i
			for j < N && S[i] == S[j] {
				j++
			}
			ch := S[i]
			count := j - i
			if ch == '0' {
				tot += count
			} else {
				for k := 0; k < count/2; k++ {
					v = append(v, tot)
				}
			}
			i = j
		}

		m := len(v)
		dp1 := make([][]int, m+1)
		dp2 := make([][]int, m+1)
		for i := range dp1 {
			dp1[i] = make([]int, tot+1)
			dp2[i] = make([]int, tot+1)
		}
		dp1[0][0] = 1

		for i := 0; i <= m; i++ {
			for j := 0; j <= tot; j++ {
				if i < m {
					dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j]) % MOD
					term := dp1[i][j] * abs(v[i]-j) % MOD
					dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j] + term) % MOD
				}
				if j+1 <= tot {
					dp1[i][j+1] = (dp1[i][j+1] + dp1[i][j]) % MOD
					dp2[i][j+1] = (dp2[i][j+1] + dp2[i][j]) % MOD
				}
			}
		}

		fmt.Println(dp2[m][tot])
	}
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            String S = br.readLine();
            
            List<Integer> v = new ArrayList<>();
            int tot = 0;
            int i = 0;
            while (i < N) {
                int j = i;
                while (j < N && S.charAt(i) == S.charAt(j)) {
                    j++;
                }
                char ch = S.charAt(i);
                int count = j - i;
                if (ch == '0') {
                    tot += count;
                } else {
                    for (int k = 0; k < count / 2; k++) {
                        v.add(tot);
                    }
                }
                i = j;
            }
            
            int m = v.size();
            int[][] dp1 = new int[m + 1][tot + 1];
            int[][] dp2 = new int[m + 1][tot + 1];
            dp1[0][0] = 1;
            
            for (i = 0; i <= m; i++) {
                for (int j = 0; j <= tot; j++) {
                    if (i < m) {
                        dp1[i + 1][j] = (dp1[i + 1][j] + dp1[i][j]) % MOD;
                        dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]) % MOD;
                        long add = (long) dp1[i][j] * Math.abs(v.get(i) - j) % MOD;
                        dp2[i + 1][j] = (int) ((dp2[i + 1][j] + add) % MOD);
                    }
                    if (j < tot) {
                        dp1[i][j + 1] = (dp1[i][j + 1] + dp1[i][j]) % MOD;
                        dp2[i][j + 1] = (dp2[i][j + 1] + dp2[i][j]) % MOD;
                    }
                }
            }
            
            pw.println(dp2[m][tot]);
        }
        pw.close();
    }
}

JavaScript solution:
const MOD = 998244353;

function solve() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    let ptr = 0;
    const T = parseInt(input[ptr++], 10);
    for (let _ = 0; _ < T; _++) {
        const N = parseInt(input[ptr++], 10);
        const S = input[ptr++].trim();
        
        const v = [];
        let tot = 0;
        let i = 0;
        while (i < N) {
            let j = i;
            while (j < N && S[i] === S[j]) {
                j++;
            }
            const ch = S[i];
            const count = j - i;
            if (ch === '0') {
                tot += count;
            } else {
                const segments = Math.floor(count / 2);
                for (let k = 0; k < segments; k++) {
                    v.push(tot);
                }
            }
            i = j;
        }
        
        const m = v.length;
        const dp1 = Array.from({ length: m + 1 }, () => new Array(tot + 1).fill(0));
        const dp2 = Array.from({ length: m + 1 }, () => new Array(tot + 1).fill(0));
        dp1[0][0] = 1;
        
        for (let i = 0; i <= m; i++) {
            for (let j = 0; j <= tot; j++) {
                if (j + 1 <= tot) {
                    dp1[i][j + 1] = (dp1[i][j + 1] + dp1[i][j]) % MOD;
                    dp2[i][j + 1] = (dp2[i][j + 1] + dp2[i][j]) % MOD;
                }
                if (i < m) {
                    dp1[i + 1][j] = (dp1[i + 1][j] + dp1[i][j]) % MOD;
                    const diff = Math.abs(v[i] - j);
                    dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j] + dp1[i][j] * diff) % MOD;
                }
            }
        }
        
        console.log(dp2[m][tot]);
    }
}

solve();

Python solution:
# cook your dish here
for i in range(int(input())):
    n = int(input())
    s = input()

    v = []
    tot = 0
    i = 0
    while i < n:
        j = i
        while j < n and s[i] == s[j]:
            j += 1
        ch = s[i]
        count = j - i
        if ch == '0':
            tot += count
        else:
            v.extend([tot] * (count // 2))
        i = j

    m = len(v)
    dp1 = [[0] * (tot + 1) for _ in range(m + 1)]
    dp2 = [[0] * (tot + 1) for _ in range(m + 1)]
    dp1[0][0] = 1

    for i in range(m + 1):
        for j in range(tot + 1):
            if j + 1 <= tot:
                dp1[i][j + 1] = (dp1[i][j + 1] + dp1[i][j]) % 998244353
                dp2[i][j + 1] = (dp2[i][j + 1] + dp2[i][j]) % 998244353
            if i < m:
                dp1[i + 1][j] = (dp1[i + 1][j] + dp1[i][j]) % 998244353
                dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j] + dp1[i][j] * abs(v[i] - j)) % 998244353

    print(dp2[m][tot])

Ruby solution:
MOD = 998244353

def solve
  t = gets.to_i
  t.times do
    n = gets.to_i
    s = gets.chomp

    v = []
    tot = 0
    i = 0
    while i < n
      j = i
      while j < n && s[i] == s[j]
        j += 1
      end
      ch = s[i]
      count = j - i
      if ch == '0'
        tot += count
      else
        (count / 2).times do
          v << tot
        end
      end
      i = j
    end

    m = v.size
    dp1 = Array.new(m + 1) { Array.new(tot + 1, 0) }
    dp2 = Array.new(m + 1) { Array.new(tot + 1, 0) }
    dp1[0][0] = 1

    (0..m).each do |i|
      (0..tot).each do |j|
        if j + 1 <= tot
          dp1[i][j + 1] = (dp1[i][j + 1] + dp1[i][j]) % MOD
          dp2[i][j + 1] = (dp2[i][j + 1] + dp2[i][j]) % MOD
        end
        if i < m
          dp1[i + 1][j] = (dp1[i + 1][j] + dp1[i][j]) % MOD
          dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j] + dp1[i][j] * (v[i] - j).abs) % MOD
        end
      end
    end

    puts dp2[m][tot]
  end
end

solve