2023-01-08：小红定义一个仅有 r、e、d 三种字符的字符串中， 如果仅有一个长度不小于 2 的回文子串，那么这个字符串定义为“好串“。 给定一个正整数 n，输出长度为 n 的好串有多少个。 结果对 10^9

use std::iter::repeat;fn main() {    for i in 1..=10 {        println!("长度为{}, 答案:{},{}", i, num1(i), num2(i));    }}
// 暴力方法// 为了观察规律// 具体方法论，在体系学习班，章节39 : 根据对数器找规律fn num1(n: i32) -> i32 {    let mut p: Vec<u8> = repeat(0).take(n as usize).collect();    return process1(&mut p, 0);}
fn process1(p: &mut Vec<u8>, i: i32) -> i32 {    if i == p.len() as i32 {        let mut dp = get_manacher_dp(p);        let mut cnt = 0;        for p in dp.iter() {            if p - 1 > 3 {                return 0;            }            if p - 1 >= 2 {                cnt += 1;            }            if cnt > 1 {                return 0;            }        }        return if cnt == 1 { 1 } else { 0 };    } else {        let mut ans = 0;        p[i as usize] = 'r' as u8;        ans += process1(p, i + 1);        p[i as usize] = 'e' as u8;        ans += process1(p, i + 1);        p[i as usize] = 'd' as u8;        ans += process1(p, i + 1);        return ans;    }}
fn get_manacher_dp(s: &mut Vec<u8>) -> Vec<i32> {    let mut str = manacher_string(s);    let mut p_arr: Vec<i32> = repeat(0).take(str.len()).collect();    let mut cc = -1;    let mut rr = -1;    for i in 0..str.len() as i32 {        p_arr[i as usize] = if rr > i {            get_min(p_arr[(2 * cc - i) as usize], rr - i)        } else {            1        };        while i + p_arr[i as usize] < str.len() as i32 && i - p_arr[i as usize] > -1 {            if str[(i + p_arr[i as usize]) as usize] == str[(i - p_arr[i as usize]) as usize] {                p_arr[i as usize] += 1;            } else {                break;            }        }        if i + p_arr[i as usize] > rr {            rr = i + p_arr[i as usize];            cc = i;        }    }    return p_arr;}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}
fn manacher_string(s: &mut Vec<u8>) -> Vec<u8> {    let mut res: Vec<u8> = repeat(0).take(s.len() * 2 + 1).collect();    let mut index = 0;    let mut i = 0;    while i != res.len() {        res[i as usize] = if (i & 1) == 0 {            '#' as u8        } else {            index += 1;            s[index - 1]        };        i += 1;    }    return res;}
// 正式方法// 观察规律之后，把规律变成代码fn num2(n: i32) -> i32 {    if n == 1 {        return 0;    }    if n == 2 {        return 3;    }    if n == 3 {        return 18;    }    return 6 * (n + 1);}

// SPDX-License-Identifier: MITpragma solidity ^0.8.17;
contract Hello{    function main() public pure returns (int32[] memory){        int32[] memory ans = new int32[](10);    for (int32 i = 1; i <= 10; i++) {      ans[uint32(i-1)] = num2(i);    }    return ans;    }
  // 正式方法  // 观察规律之后，把规律变成代码  function  num2(int32 n) public pure returns(int32) {    if (n == 1) {      return 0;    }    if (n == 2) {      return 3;    }    if (n == 3) {      return 18;    }    return 6 * (n + 1);  }
}